Logic Blog 2016

Editor: Andr\'e Nies

1. Westrick: randomness and rotations of the unit circle

The following result was obtained at the computability retreat at Research Centre Coromandel in February. It started through discussions between Adam Day, Andre Nies, Dan Turetsky and Brown Westrick.

\vsp

Let P[0,1]P\sub[0,1] be a Π10\Pi^0_1 class. \begin{thm} Let XMLRX \in MLR. Let kNk\in \NN. 1. There is a rational number q0q \neq 0 such that for all iki\leq k, X+qiPX + qi \in P. 2. Let α\alpha be a computable irrational number. There is an integer n0n \neq 0 such that for all iki\leq k, (X+αnimod1)P(X + \alpha n i \mod 1) \in P. \end{thm} \begin{proof}

Both (1) and (2) are proved by the same method. Dynamically construct a Solovay test as follows. Put the empty string \estring in the test. Then for any σ\sigma that has been placed in the test, let rσr_\sigma be a rational number (for (1)) or let nσ>0n_\sigma \gt 0 be an integer (for (2)) such that \bc 2σ2k+3<rσ,(αnσmod1)<2σ2k+2\frac{2^{-|\sigma|}}{2k+3} \lt r_\sigma, (\alpha n_\sigma \mod 1) \lt \frac{2^{-|\sigma|}}{2k+2}. \ec These bounds are chosen so that for every z[σ]z \in [\sigma], z+krσ[σ]z + kr_\sigma \in [\sigma] or zkrσ[σ]z - kr_\sigma \in [\sigma]. Let UsU_s denote the complement of PP as seen at stage ss. We will enumerate τ\tau into the test at stage ss if we see the following occur: 1. στ\sigma \prec \tau, 2. τ\tau is incomparable with any τ\tau' which has already entered the test on the basis of this same σ\sigma 3. [τ]Us=[\tau] \cap U_s = \emptyset 4. For some integer i[k,k]i \in [-k, k], [τ]+irσ[σ]Us[\tau] + i r_\sigma \subseteq [\sigma]\cap U_s. The point is to enumerate [τ][\tau] if its potential ±rσ\pm r_\sigma kk-recurrence inside [σ][\sigma] is invalidated. For (2), replace rσr_\sigma everywhere with αnσmod1\alpha n_\sigma \mod 1.

The test catches any zPz\in P which fails to kk-recur for all rQ{0}r \in \mathbb{Q}\setminus \{0\} (resp. for all αn\alpha n with nZ{0}n \in \mathbb{Z}\setminus \{0\}). We need to show it is a Solovay test.

We show that for every σ\sigma in the test, the total measure of all τ\tau added to the test as a result of σ\sigma is at most 2k+22k+3μ[σ]\frac{2k+2}{2k+3} \mu [\sigma]. So if the depth of τ\tau is the number of initial segments that τ\tau has in the test, then μ({[τ]:τ of depth d})(2k+22k+3)d\mu(\cup\{[\tau] : \tau \text{ of depth } d\}) \leq \left(\frac{2k+2}{2k+3}\right)^d, so this will suffice to show that the total measure of the test is finite.

When σ\sigma is first put in the test, [σ][\sigma] is disjoint from UsU_s. When first ρ\rho enters UsU_s with σρ\sigma \prec \rho, we can consider [σ][\sigma] as being divided into two parts, both invariant under addition of rσr_\sigma: C={z[σ]:z+irσ[ρ]C=\{z \in [\sigma] : z + ir_\sigma \in [\rho] for some iZ}i \in \mathbb{Z}\}, and its complement. All zz whose initial segments could potentially be enumerated as a result of ρ\rho are contained in CC. Also [ρ]C[\rho]\subseteq C, but nothing comparable with ρ\rho will be enumerated. By the choice of rσr_\sigma, μ[ρ]μC12k+3\frac{\mu[\rho]}{\mu C} \leq \frac{1}{2k+3}. Therefore, the measure added to the test as a result of the addition of ρ\rho, and as a result of the addition of any future ρ\rho' with [ρ]C[\rho'] \subseteq C, is bounded by 2k+22k+3μC\frac{2k+2}{2k+3}\mu C.

The remaining set [σ]C[\sigma] \setminus C is currently untouched but may in the future be seen to intersect the complement of PP. When that happens, we apply the same reasoning inside of [σ]C[\sigma]\setminus C, partitioning it into two invariant pieces and arguing that one piece remains untouched, while the other can never contribute more than 2k+22k+3\frac{2k+2}{2k+3} of its measure to the test. Continuing in this way, we get the desired bound on the measure the test uses in response to σ\sigma. \end{proof}


2. Nies: alternative proof of Thm.\ \ref{thm:multiple recurrence

(1)}

The case k=1k=1 of the theorem can be derived from a result of Figueira et al.\ 14; also see \cite[3.3.7]{Nies:book}. That theorem of 14 says that if XX is not autoreducible, then there is a bit position nn such that the bit nn is indifferent for XX with respect to PP, which means that we can change XX at nn and remain in PP. This change corresponds to adding or subtracting the rational 2n\tp{-n}.

Now let us obtain an arithmetical progression namely X+qiPX + qi \in P for i<k/2i \lt k/2 (for technical reasons).

At first we work with ZkωZ\in k^\omega. Extending the case of k=2k=2, we say that ZZ is auto-reducible if there is a reduction procedure Φ\Phi such that ΦZ(n)Z(n)\Phi^Z(n) \neq Z(n) for each nn, and the computation ΦZ(n)\Phi^Z(n) only queries the oracle at values other than nn. As before, one checks that a ML-random sequence ZZ is not auto-reducible. We say that position nn is indifferent for ZZ with respect to a Π10\PI 1 class PkωP\sub k^\omega if we can change ZZ at nn to any value <k\lt k and remain in PP.

\begin{prop} Let QkωQ\sub k^\omega be a Π10\PPI class. If ZQZ \in Q is not autoreducible, then there is a position nn such that the bit nn is indifferent for ZZ with respect to QQ. \end{prop} \begin{proof} A straightforward extension of the argument for k=2k=2. If there is no such position, given input nn the reduction Φ\Phi searches for a stage ss and i<ki \lt k such that ZZ, with position nn changed to value ii, is not in QQ, and once found, output this ii. \end{proof}

To obtain the arithmetical progression assume that k=2rk= \tp r for rNr \in \NN. Given Π10\PPI class P2NP \sub \cantor and ML-random XPX\in P , let QQ, ZZ be the class/sequence rewritten using the alphabet 0,,k10, \ldots, k-1. That is, the block bits of XX in positions nr(n+1)r1nr \ldots (n+1)r -1 corresponds the symbol of ZZ in position nn. If nn is indifferent for ZZ in QQ, then we have an arithmetical progression X+qiPX + qi\in P, where i<k/2i \lt k/2, q=±2rnq = \pm \tp{-rn}.

\part{Randomness via algorithmic tests}


3. Smart sets for arbitrary cost functions

\newcommand{\conc}{\hat{\,\,}}

\newcommand{\cost}{\mathbf{c}} \newcommand{\dost}{\mathbf{d}} \newcommand{\cc}{\mathbf{c}} \newcommand{\limcost}{\underline{\cost}} \newcommand{\converge}{\!\!\downarrow}

\newcommand \sinit {s_{\mathrm{init}}}

The following is work of Greenberg, Miller, Nies and Turetsky at RCC in Feb.\ 2015, and in Wellington slightly later. For background on cost functions see 30. In the following all cost functions satisfy the limit condition limx\cost(x)=0\lim_x \cost(x) = 0.

\begin{definition}[3] Let \cost\cost be a cost function. A descending sequence \seq{V_n} of uniformly c.e.\ open sets is a \cost\cost-bounded test if λ(Vn)=O(\limcost(n))\leb(V_n) =O( \limcost(n)) for all nn. \end{definition} We think of each VnV_n as an approximation for YkVkY\in \bigcap_k V_k. Being in nVn\bigcap_n V_n can be viewed as a new sense of obeying \cost\cost that makes sense for ML-random sets. \begin{lemma} Suppose aYaY fails a \cost\cost-bounded test nVn\bigcap_n V_n where a{0,1}a \in \{0,1\}. Then YY fails a \cost\cost-bounded test. \end{lemma}

\begin{proof} We may suppose a=0a=0 and XVnX \in V_n implies X(0)=0X(0) =0. Since λT(Vn)2λVn\leb T (V_n )\le 2 \leb V_n where TT is the usual shift operator on Cantor space, (T(Vn)i)iN\seq{ T (V_n)} is also a \cost\cost-bounded test. Clearly YY fails it. \end{proof}

The basic motivating result is a generalisation in terms of cost functions of a fact of Hirschfeldt and Miller. \begin{prop} If A\costA \models \cost and YY is a ML-random captured by a \cost\cost-bounded test, then ATYA \leT Y. \end{prop}

The most powerful kind of set obeying a given cost function

The following is the central definition for this entry: given \cost\cost, we consider sets AA such that the converse implication holds as well. \begin{definition} Let \cost\cost be a cost function and AA be a Δ20\DII set. We say that AA is smart for \cost\cost if A\costA \models \cost and for each ML-random set YY, \begin{center} YY is captured by a \cost\cost-bounded test ATY\LR A \leT Y. \end{center} \end{definition}

Informally, if AA is smart for \cost\cost then AA is as complex as possible among the sets obeying \cost\cost, in the sense that the only random sets YY above AA are the ones that have to be there because AA obeys the cost function that puts it below YY anyway.

\begin{theorem} Let \cost\cost be a cost function with \cost\costΩ\cost \to \cost_\Omega. Some c.e.\ set AA is smart for \cost\cost. \end{theorem}

\begin{proof} Recall Υ\Upsilon is a ``universal" Turing functional in the sense that Υ(0e1\concX)=Φe(X)\Upsilon({0^e1}\conc{X}) = \Phi_e(X) for each X,eX,e. We build AA and a \cost\cost-test \seq{\+ U_k} capturing any ML-random YY such that A=ΥYA = \Upsilon^Y. This suffices for the theorem by Lemma~ ?.

Since 2x×ΩΩx2^{-x}\le^\times \Omega - \Omega_x, we may assume that \cost(x,s)2x\cost(x,s) \ge \tp{-x} for xsx \le s.

As in 3, during the construction of AA we build a global ``error set":

\[ \+ E_s = \{ Y \colon \ex n\, [ \Upsilon^Y_s(n)\converge=0 \lland A_s(n) = 1 ]\}\]

All all stages ss we will have \[ \tag{\diamond} \leb \+ U_{k,s} \le \cost(k,s) + \leb ( \+ E_{s+1} - \+ E_k). \] So since λ(\+E\+Ek)×\costΩ(k)\leb (\+ E - \+ E_k) \le^\times \cost_ \Omega(k) and \costΩ(k)×\limcost(k)\cost_\Omega(k) \le^\times\limcost(k), the test \seq{\+ U_k} is indeed a \cost\cost-test.

We reserve the interval Ik=[2k,2k+1)I_k = [\tp k, \tp{k+1} ) for ensuring (\diamond). The construction of \+Uk\+ U_k is as follows. At stage s>ks \gt k, let x=min(IkAs1)x = \min (I_k - A_{s-1}). Let \[ \+ U_{k,s} = \bigcup_{t\diamond) threatens to fail at ss, namely λ\+Uk,s>\cost(k,s)+λ(\+Es\+Ek)\leb \+ U_{k,s} \gt \cost(k,s) + \leb ( \+ E_s - \+ E_k), put xx into As+1A_{s+1}. This causes \+Uk,s\+ U_{k,s} to go into \+Es+1\+ E_{s+1}.

First we verify that xx always exists, that is, we enumerate at most 2k\tp k times for \+Uk\+ U_k. If we do this at stage ss, λ\+Uk,s>2k+λ(\+Es\+Ek)\leb\+ U_{k,s} \gt 2^{-k} + \leb(\+ E_s - \+E_k). Since \+Uk,s\+Ek=\+U_{k,s} \cap \+E_k = \emptyset by definition, and \+Uk,s\+Es+1\+U_{k,s} \subseteq \+E_{s+1}, it follows that λ(\+Es+1\+Es)>2k\leb(\+E_{s+1} - \+E_s) \gt 2^{-k}. Since λ\+E1\leb \+E \le 1, this can happen at most 2k2^k times.

In particular, if A=ΥZA = \Upsilon^Z then Zk\+UkZ \in \bigcap_k \+ U_k. It remains to verify that A\costA \models \cost. If we enumerate xx for \+Uk\+ U_k at stage ss then \[ \leb (\+ U_{k,s} - \+ E_s) = \leb (\+ U_{k,s} - (\+ E_s - \+ E_k) ) \ge \leb (\+ U_{k,s} ) - \leb(\+ E_s - \+ E_k) > \cost(k,s ) \ge \cost (x,s). \] Since \+Uk,s\+Es\+Es+1\+Es\+ U_{k,s} - \+ E_s \sub \+ E_{s+1} - \+ E_s, we see that \cost(x,s)<λ(\+Es+1\+Es)\cost(x,s) \lt \leb(\+E_{s+1} - \+E_s). This implies that the total cost of the enumeration of AA is at most 11. \end{proof}

ML-reducibility

\begin{definition}[3] For KK-trivial sets AA and BB, we write BMLAB \le_{\textup{ML}} A if ATYA \leT Y implies BTYB \leT Y for any ML-random set YY. \end{definition} Clearly, T\leT implies ML\le_{\textup{ML}}. The ML-degrees form an upper semilattice where the least upper bound of KK-trivial sets CC and DD is given by the KK-trivial set CDC \oplus D.

\begin{definition} Let \cost\cost be a cost function and AA be a Δ20\DII set. We say that AA is ML-complete for \cost\cost if A\costA \models \cost, and B[B\costBMLA]\fa B \, [B \models \cost \RA B \le_{ML} A]. \end{definition} \begin{cor} AA is smart for \cost\cost \LR AA is ML-complete for \cost\cost. \end{cor} \begin{proof} \RA: Suppose ATYA\leT Y for ML-random YY. Then some \cost\cost-bounded test captures YY. If B\costB \models \cost, then BTYB \leT Y by the basic fact~ ?. Thus BMLAB \le_{ML} A as required.

\noindent \LA: By Theorem~ ? let A~\wt A be smart for \cost\cost. Suppose ATYA \leT Y for ML-random YY; we want to show that YY is captured by a \cost\cost-bounded test. Since AA is ML-complete for \cost\cost we have A~MLA\wt A \le_{ML} A, so A~TY\wt A \leT Y, so YY is captured by a \cost\cost-bounded test as required. \end{proof} In particular, the ML-degree of a smart set AA for \cost\cost is uniquely determined by \cost\cost. On the other hand, for each low c.e.\ set AA there is a c.e.\ set B̸TAB \not \le_T A such that B\costB \models \cost \cite[5.3.22]{Nies:book}. If AA is smart for \cost\cost, then ABA \oplus B is also smart for \cost\cost. As each KK-trivial is low, the Turing degree of a set AA that is smart for \cost\cost is not uniquely determined by \cost\cost.

\begin{question} Given \cost\cost can we build a smart for \cost\cost set AA that is cappable? Can we even have two smart for \cost\cost sets that form a minimal pair? \end{question}

The strongest cost function obeyed by a given set

Given c.e.\ KK-trivial AA we will define a c.f.\ \costA\cost_A with A\costAA \models \cost_A such that every random computing AA is captured by a \costA\cost_A test. (In other words, AA is smart for cAc_A.) However, \costA\cost_A may not be a very natural cost function. We build a KK-trivial AA such that the class of sets obeying \costA\cost_A is not closed downward under T\leT, and in fact not even the shift T(A)T(A) obeys \costA\cost_A. As before Υ\Upsilon denotes a ``universal" Turing functional. Given a c.e.\ KK-trivial set AA, fix a c.e.\ approximation \seq{A_s} \models \cost_\Omega. We let \[ \cost_A(x,s) = \leb \bigcup_{x\le t< s} \{ Y \colon A_t \uhr {x+1} \preceq \Upsilon_t^Y \}.\] \begin{prop} (i) A\costAA \models \cost_A. (ii) Suppose \cost\cost is a cost function such that A\costA \models \cost. Then \costA\cost\cost_A \to \cost. In particular, \costA\costΩ\cost_A \to \cost_\Omega. \end{prop} \begin{proof} (i) We show that the fixed approximation \seq{A_s} \models \cost_A. Define the left-c.e.\ ``error real'' by: \[ \epsilon_s = \leb\{Y : \exists n [\Upsilon^Y_s(n)\converge=0 \wedge A_s(n) =1]\} \] Note that if xAsAs1x \in A_s - A_{s-1}, then \costA(x,s)ϵsϵx=\costϵ(x,s)\cost_A(x,s) \le \epsilon_s - \epsilon_x = \cost_\epsilon(x,s). So \cost_A\seq{A_s} \le \cost_\epsilon\seq{A_s}. Since \costΩ\costϵ\cost_\Omega \to \cost_\epsilon, and \seq{A_s} \models \cost_\Omega, it follows that \seq{A_s} \models \cost_A. (ii) By multiplying by a constant, we may assume that \cost(0)<1/2\cost(0) \lt 1/2. Fix a computable speed-up ff such that \cost\seq{A_{f(s)}} \lt 1/2. Define a Turing functional Ψ\Psi such that at every stage f(s)f(s), λ{Y:Af(s) ⁣x+1Ψf(s)Y}=\cost(x,s)\leb\{Y : A_{f(s)}\uhr{x+1} \prec \Psi^Y_{f(s)} \} = \cost(x,s). By a simple argument, the measure of the error-set \+E\+E for this functional will be \cost\seq{A_{f(s)}} \lt 1/2, so this construction may proceed. Fix ee with Φe=Ψ\Phi_e = \Psi. Then \limcostA(x)2(e+1)\limcost(x)\limcost_A(x) \ge 2^{-(e+1)} \limcost(x). \end{proof}

Recall that T(A)T(A) is the shift of AA. \begin{thm} For each cost function \dost\dost, there is a cost function \cost\dost\cost \ge \dost and a c.e.\ set AA such that A\costA \models \cost and T(A)⊭\costT(A) \not \models \cost. \end{thm} Since \costA\cost\cost_A \to \cost, this shows that T(A)⊭\costAT(A) \not \models \cost_A. \begin{proof} We fix a listing \seq{\Phi_e} of all (possibly partial) computable enumerations \seq{B_t}, where BtDΦe(t)B_t \simeq D_{\Phi_e(t)} and DΦe(t)DΦe(t+1)D_{\Phi_e(t)} \sub D_{\Phi_e(t+1)} if defined. We may assume \dost(s1,s)2s\dost(s-1, s) \ge \tp{-s}. We define \cost(x,s)\cost(x,s) so that \cost(x,s)\dost(x,s)\cost(x,s) \ge \dost(x,s) for each x,sx,s. At a stage xx of the construction we may also declare that \cost(x1,x)α\cost(x-1,x) \ge \alpha, which by monotonicity entails that \cost(y,s)α\cost(y, s) \ge \alpha for each y<xy<x and sxs \ge x. We meet the requirements

\[R_e \colon \, T(A) = \bigcup_t D_{\Phi_e(t)} \RA \cost \seq {\Phi_e} \ge 1. \] The strategy for ReR_e tries to ensure \limcost(x1)\limcost (x-1) is large and \limcost(x)\limcost(x) is small for sufficiently many xx. In that case ReR_e can put xx into AA for the small cost, while the opponent's enumeration \seq{\Phi_e} of T(A)T(A) has to deal with the large cost. One problems in implementing this idea is the timing as we will of Φe(u)\Phi_e (u) for a stage uu only at a stage ss much larger than uu. Also we always have \cost(x,s)\dost(x,s)\cost(x,s) \ge \dost(x,s), so once we discover that the enumeration of xx would help because \seq{\Phi_e} caught up sufficiently much, it may be that the enumeration of xx has become too expensive for ReR_e. Similar to the usual construction of a set obeying \dost\dost, in this case we simply pick a new xx. Since \dost\dost has the limit condition, eventually we will always be able to keep xx. At a stage s>0s \gt 0 let s\init(e)s_{\init}(e) be the greatest stage t<st\lt s such that t=0t=0 or ReR_e has been initialised at tt. If by stage ss the strategy for ReR_e has been initialised for bb times it can spend a \cost\cost-cost of 2be\tp{-b-e} in enumerating AA. It is also allowed to raise \cost(x,s)\cost(x,s) to 2\sinit(e)\tp{-\sinit(e)}. The ee-expansionary stages are the ones at which \seq {\Phi_e} catches up with T(A)T(A). We declare 00 as ee-expansionary. A stage s>0s>0 is ee-expansionary if for the largest ee-expansionary stage t<st<s, we have that T(As) ⁣t+2=Φe,s(u) ⁣t+2T(A_s)\uhr{t+2} = \Phi_{e,s}(u) \uhr {t+2} where uu is largest such that Φe,s(u)\Phi_{e,s}(u) is defined and u>tu>t. \noindent Strategy for ReR_e. Write α=2\sinit(e)\alpha = \tp{-\sinit(e)}. A rational parameter γe[0,1]\gamma_e \in [0,1] measures progress of ReR_e. We set γe\gamma_e to 00 when ReR_e is initialised. At ee-expansionary stage ss, if γe1\gamma_e \le 1 do the following. Initialize lower priority requirements. Declare that \cost(s1,s+1)α\cost (s-1,s+1) \ge \alpha. (So for Φe\Phi_e, changing at s1s-1 will be expensive after stage ss.) Let x<sx \lt s be the last ee-expansionary stage. If \dost(x,s)<2beα\dost(x,s) \lt \tp{-b-e} \alpha, put xx into AsA_{s} (note that no-one has raised the \cost\cost cost for xx above \dost(x,s)\dost(x,s) yet), add α\alpha to γe\gamma_e. Say that ReR_e acts.

Clearly ReR_e only acts 2\sinit(e)=1/α\tp{\sinit(e)}= 1/\alpha times while it is not initialised. \begin{claim} A\costA \models \cost. \end{claim} When ReR_e acts at ss we have \cost(x,s)2beα\cost(x,s)\le \tp{-b-e} \alpha by initialisation. \begin{claim} TA⊭\costTA \not \models \cost. \end{claim} Otherwise TA\costTA \models \cost via some enumeration \seq {\Phi_e} such that \cost \seq {\Phi_e} \lt 1. Since \dost\dost satisfies the limit condition, γe\gamma_e reaches the value 11. This is at least what \seq {\Phi_e} pays for the enumerations of x1x-1 into TATA. For when ReR_e acts at ss via xx then x1∉Φe(u)x-1 \not \in \Phi_e(u) for some u>xu>x since ss is ee-expansionary. By the next ee-expansionary stage we have x1Φe(u)x-1 \in \Phi_e(u') for some u>uu' \gt u. So Φe\Phi_e paid the cost \cost(x1,x+1)α\cost(x-1,x+1) \ge \alpha that was set by ReR_e at stage xx. \end{proof}

\part{Computability theory}


4. Merkle, Nies and Stephan: A dual of the Gamma question

Merkle, Nies and Stephan worked at NUS in February. They considered a dual of the Γ\Gamma operator on Turing degrees.

For ZNZ\sub \NN the lower density is defined to be

ρ(Z)=lim infnZ[0,n)n.\underline \rho (Z) = \liminf_n \frac{|Z \cap [0, n)|}{n}.

Recall that

γ(A)=supXcomputableρ(AX)\gamma(A)=\sup_{X \, \text{computable}} \underline \rho(A\leftrightarrow X)

Γ(A)=inf{γ(Y) ⁣:YTA}\Gamma(A) = \inf \{ \gamma(Y) \colon \, Y \le_T A \}

which only depends on the Turing degree of AA. The Γ\Gamma operator was introduced by Andrews, Cai, Diamondstone, Jockusch and Lempp 1. \begin{definition}

δ(A)=infXcomputableρ(AX)\delta(A)=\inf_{X \, \text{computable}} \underline \rho(A\leftrightarrow X)

Δ(A)=sup{δ(Y) ⁣:YTA}.\Delta(A) = \sup \{ \delta(Y) \colon \, Y \le_T A \}.

\end{definition} Intuitively, \bi \item Γ(A)\Gamma(A) measures how well computable sets can approximate the sets that AA computes, counting the asymptotically worst case (the infimum over all YTAY \le_T A). In contrast, \item Δ(A)\Delta(A) measures how well the sets that AA computes can approximate the computable sets, counting the asymptotically best case (the supremum over all YTAY \le_T A). \ei Clearly the maximum value of Δ(A)\Delta(A) is 1/21/2. The operator Δ(A)\Delta(A) is related to the analog of a cardinal characteristic introduced by Brendle and Nies in the 2015 Logic Blog~12. They define \+B(p)\+ B(\sim_p) to be the class of oracles AA that compute a set YY such that for each computable set XX, we have ρ(XY)>p\ul \rho (X \lra Y) \gt p. For each pp with 0p<1/20 \le p \lt 1/2, \bc Δ(A)>pA\+B(p)Δ(A)p\Delta(A) \gt p \RA A \in \+ B(\sim_p) \RA \Delta(A) \ge p. \ec We state three minor results. \begin{prop} Let AA be 2-generic. Then Δ(A)=0\Delta(A)=0. \end{prop} A proof is given at the end of Section~Section 2.

\begin{prop} Let AA compute a Schnorr random YY. Then Δ(A)=1/2\Delta(A) = 1/2. \end{prop} This is clear because ρ(YR)=1/2\underline \rho(Y\leftrightarrow R)=1/2 for each computable RR.

\begin{prop} Let p(0,1/2)p\in (0,1/2) be computable. Let AA be Schnorr random for the Bernoulli measure w.r.t.\ pp. Then δ(B)=p\delta(B) =p for each B1AB \equiv_1 A. \end{prop}

The ``Δ\Delta-question" is (or rather, was, and has been quite short-lived):

\begin{question}[solved] Can Δ(A)\Delta(A) be properly between 00 and 1/21/2? \end{question} Using a dual form of Monin's technique's below, this has been answered in the negative by Nies; see Section~Section 2.


5. Monin - A resolution of the Gamma question

We show that there is no sequence XX with a Gamma value strictly between 00 and 1/21/2.

\begin{definition} For a given nωn \in \omega and two strings σ1,σ22n\s_1, \s_2 \in 2^n, the notation d(σ1,σ2)d(\s_1, \s_2) denotes the normalised hamming distance between σ1\s_1 and σ2\s_2, that is, the number of bits on which σ1\s_1 and σ2\s_2 differ divided by nn. \end{definition}

\begin{definition} Let F:ωωF:\omega \rightarrow \omega be a function. Given a function ff such that f(n)<2F(n)f(n)\lt 2^{F(n)}, for each nn, by [f(n)][f(n)] we denote the string of length F(n)F(n) encoded by f(n)f(n). \end{definition}

The following weakens the notion of infinitely often equal (i.o.e.) for a computable bound, which was first studied in 29. \begin{definition} Let F:ωωF:\omega \rightarrow \omega be a function and α[0,1]\alpha \in [0,1]. A function ff is 2F(n)2^{F(n)}-infinitely often α\alpha-equal if for every computable function g:ωωg:\omega \rightarrow \omega which is bounded by 2F(n)2^{F(n)}, we have:

lim infnd([f(n)],[g(n)])1α\liminf_{n} d([f(n)], [g(n)]) \leq 1 - \alpha

Informally, we want ff to equal infinitely often on a fraction of at least α\alpha bits, to every computable function bounded by 2F(n)2^{F(n)}. Typically we will have α>1/2\alpha \gt 1/2.

\end{definition}

\begin{proposition} Let 1/2<α<11/2 \lt \alpha \lt 1. Suppose that for no kk, XX computes a function which is 22n/k2^{\lfloor 2^{n/k} \rfloor}-i.o.α\alpha-e. Then Γ(X)1α\Gamma(X) \geq 1 - \alpha. \end{proposition} \begin{proof} Consider any sequence YY computed by XX. Fix some cωc \in \omega and let kk be the smallest integer such that 21/k1<1/(2c)2^{1/k} - 1 \lt 1/(2c). We then split YY in blocks of bits of length 2n/k\lfloor 2^{n/k} \rfloor. We now argue that for nn large enough, the number of bits in the n+1n+1-th block is smaller than 1/c1/c times the sum of the number of bits in the previous blocks. By the sum of geometric series we have:

i=0in2i/k=2(n+1)/k121/k1\sum_{i=0}^{i \leq n} 2^{i/k} = \frac{2^{(n+1)/k} - 1}{2^{1/k} - 1}

which implies that

2(n+1)/k1=(21/k1)i=0in2i/k12ci=0in2i/k\begin{array}{rcl} 2^{(n+1)/k} - 1&=&(2^{1/k} - 1)\sum_{i=0}^{i \leq n} 2^{i/k}\\ &\leq&\frac{1}{2c}\sum_{i=0}^{i \leq n} 2^{i/k}\\ \end{array}

For nn large enough we have 12i=0in2i/k>(n+c)\frac{1}{2} \sum_{i=0}^{i \leq n} 2^{i/k} \gt (n+c). Thus for nn large enough we have:

2(n+1)/k112ci=0in2i/k12ci=0in2i/k+12ci=0in2i/k1c(n+c)1c(i=0in2i/knc)1c(i=0in2i/kc)1c(i=0in2i/k)1\begin{array}{rcl} 2^{(n+1)/k} - 1&\leq&\frac{1}{2c}\sum_{i=0}^{i \leq n} 2^{i/k}\\ &\leq&\frac{1}{2c}\sum_{i=0}^{i \leq n} 2^{i/k} + \frac{1}{2c}\sum_{i=0}^{i \leq n} 2^{i/k} - \frac{1}{c}(n+c)\\ &\leq&\frac{1}{c}(\sum_{i=0}^{i \leq n} 2^{i/k} - n - c)\\ &\leq&\frac{1}{c}(\sum_{i=0}^{i \leq n} \lfloor 2^{i/k} \rfloor - c)\\ &\leq&\frac{1}{c}(\sum_{i=0}^{i \leq n} \lfloor 2^{i/k} \rfloor) - 1 \end{array}

We then have for nn large enough that:

2(n+1)/k1c(i=0in2i/k)\lfloor 2^{(n+1)/k} \rfloor \leq \frac{1}{c}(\sum_{i=0}^{i \leq n} \lfloor 2^{i/k} \rfloor)

Thus the length of the n+1n+1 block of bit is smaller than 1/c1/c of the sum of the length of the previous blocks.

Define the function f<22n/kf \lt 2^{\lfloor 2^{n/k} \rfloor} by setting f(n)f(n) to the value coded by the bits of the nn-th block. Suppose that ff is not 22n/k2^{\lfloor 2^{n/k} \rfloor} i.o.α\alpha-e. In particular there must be some computable function h22n/kh \leq 2^{\lfloor 2^{n/k} \rfloor} such that for almost every nn, [h(n)][h(n)] agrees with [f(n)][f(n)] on a fraction of strictly less than α\alpha bits. Let hh' be defined as the complement of hh bitwise. Then for almost every nn, [h(n)][h'(n)] agrees with [f(n)][f(n)] on a fraction of bits strictly bigger than 1α1-\alpha.

Now consider the bit number mm of the sequence defined by ff, starting at the begining of a block. Let m+nm+n be the last position of that block. By hypothesis, among the mm first bits (for mm large enough), there are at least m(1α)O(1)m(1-\alpha) - \mathcal{O}(1) bits which are guessed correctly by hh'. In particular, for any 1in1 \leq i \leq n, there are also at least m(1α)O(1)m(1-\alpha) - \mathcal{O}(1) bits which are guessed correctly among the m+im+i first bits. Also for any 1in1 \leq i \leq n, the number of total bits is at most m+nm + n, which is at most m+m/cm + m/c. Thus for each ii the fraction of bits which are guessed correctly before m+im+i is at least:

m(1α)O(1)m+m/c\frac{m(1-\alpha) - \mathcal{O}(1)}{m+m/c}

As mm goes to infinity, this value converges to:

1α1+1/c\frac{1-\alpha}{1+1/c}

Thus γ(Y)1α1+1/c\gamma(Y) \geq \frac{1-\alpha}{1+1/c}. We can carry out this argument for cc larger and larger, making lower bounds on γ(Y)\gamma(Y) closer and closer to 1α1-\alpha. Thus if for any kk, we can split any YY into blocks of bits as above such that the resulting function is not 22n/k2^{\lfloor 2^{n/k} \rfloor}-i.o.α\alpha-e., then γ(Y)1α\gamma(Y) \geq 1 - \alpha. By hypothesis we can do this for every YY computable by XX. Hence Γ(X)1α\Gamma(X) \geq 1 - \alpha. \end{proof}

By contrapositive, if Γ(X)<(1α)\Gamma(X) \lt (1-\alpha), for 1/2<α<11/2 \lt \alpha \lt 1, then for some kωk \in \omega, XX computes a function which is 22n/k2^{\lfloor 2^{n/k} \rfloor}-i.o.α\alpha-e. \\

We now need to borrow some technics from the field of error correcting codes. The idea is the folloing: We want to transmit some message of length mm. But some random bit flip can occur during the transmission. We want to make sure that if the percentage of error is small enough, we can still recover the original message. The idea is to use an injection Φ\Phi from 2m2^m into 2n2^n for some n>>mn \gt \gt m, in such a way that the elements in the range of Φ\Phi, are pairwise far away from each other, in the sense of the hamming distance. If dd is the smallest distance between two elements in the range of Φ\Phi, then it is clear that we can recover up to d/2d/2 error.

Also we would like nn to be not much bigger than mm (ideally a multiplicative constant). It is easy to find such a multiplicative constant allowing, to have a list of 2m2^m elements of 2n2^n, which are all at a distance of at least 1/2ϵ1/2 - \epsilon from each other, for ϵ\epsilon as small as we want. Thus it is possible to correct this way, up to a fraction 1/41/4 of error. It is not anymore possible if the fraction is bigger than 1/41/4. However, if the fraction is smaller than 1/21/2, it is possible to identify a small list of messages, among which must figure our original message. It is even possible to make the size of the list constant. Formally we use the following theorem, for which we provide a proof for completness:

\begin{theorem}[The list decoding capacity theorem] Let 0<θ<1/20 \lt \theta \lt 1/2. There exists LωL \in \omega and 0<R<10 \lt R \lt 1 as follows.

For any nn, there exists a set CC of 2Rn2^{\lfloor Rn \rfloor} many strings of length nn such that for any string σ\s of length nn, there are at most LL strings τ\tau in CC such that d(σ,τ)<θd(\s, \tau) \lt \theta. \end{theorem} \begin{proof} We prove that for parameters LL and RR well chosen, if we pick at random the strings in CC, the theorem is true with positive probability.

Let β=2(1/2θ)2log(e)\beta = 2(1/2 - \theta)^2\log(e) and pick LL such that β1L>0\beta - \frac{1}{L} \gt 0. Then pick RR such that R<β1LR \lt \beta - \frac{1}{L}.\\

Using Chernoff bounds, for any string τ\tau of length nn, the measure of the set {[σ]:σ=n and d(τ,σ)<θ}\{[\s] : |\s| = n \text{ and } d(\tau, \s) \lt \theta\} is bounded by e2(1/2θ)2n=2βne^{-2(1/2-\theta)^2n} = 2^{-\beta n}. Thus, given a string σ\s the probability that picking a string τ\tau at random gives d(σ,τ)<θd(\s, \tau) \lt \theta, is bounded by 2βn2^{- \beta n}.

Now let q=Rnq = \lfloor Rn \rfloor and let CC be a collection of 2q2^{q} strings picked at random. For any subset of L+1L+1 of these strings, the probability that a given string σ\s has a hamming distance smaller than θ\theta with each of them is bounded by 2βn(L+1)2^{-\beta n (L+1)}. Thus the probability that a given σ\s has a hamming distance smaller than θ\theta with any possible subsets of size L+1L+1 of CC is bounded by (2qL+1)2βn(L+1)\binom{2^q}{L+1} 2^{-\beta n (L+1)}. And the probability that this happens for any string σ\s is bounded by 2n(2qL+1)2βn(L+1)2^n\binom{2^q}{L+1} 2^{-\beta n (L+1)}. The following computation shows that this quantity is smaller than 11:

2n(2qL+1)2βn(L+1)2n2Rn(L+1)2βn(L+1)2n(L+1)(R1/(L+1)+β)2n(L+1)(β+1/L1/(L+1)+β)2n(L+1)((L+1L)/L(L+1))2n/L\begin{array}{rcl} 2^n\binom{2^q}{L+1} 2^{-\beta n (L+1)}&\leq&2^n 2^{R n (L+1)} 2^{-\beta n (L+1)}\\ &\leq&2^{-n(L+1)(-R - 1/(L+1) + \beta)}\\ &\leq&2^{-n(L+1)(-\beta + 1/L - 1/(L+1) + \beta)}\\ &\leq&2^{-n(L+1)((L+1 - L)/L(L+1))}\\ &\leq&2^{-n/L} \end{array}

It follows that that for any nn, if CC is a collection of 2Rn2^{\lfloor Rn \rfloor} strings of length nn that we pick at random, the probability that no string σ\s of length nn has a hamming distance smaller than θ\theta with more than LL strings of CC, is positive. In particular, for any nn, there exists such a collection of strings. \end{proof}

We can now prove that only 00, 1/21/2 and 11 can be realized by Γ\Gamma values of sequences. First by 29, if XX compute a function bounded by 2(2n)2^{(2^n)} which equals infinitely often every computable function bounded by 2(2n)2^{(2^n)}, then Γ(X)=0\Gamma(X) = 0: First, it is also easy to show that if ff is 2(2n)2^{(2^n)}-i.o.e., then for any cc, ff computes a function which is 2(2c×n)2^{(2^{c \times n})}-i.o.e. Second, it is easy to show that if ff is 2(2c×n)2^{(2^{c \times n})}-i.o.e. then γ(f)<1/(c+1)\gamma(f) \lt 1/(c+1). \begin{theorem} Let 1/2<α<11/2 \lt \alpha \lt 1. If Γ(X)<1α\Gamma(X) \lt 1-\alpha then XX is 2(2n)2^{(2^n)}-i.o.e. and hence Γ(X)=0\Gamma(X) = 0. \end{theorem} \begin{proof} Suppose Γ(X)<1α\Gamma(X) \lt 1-\alpha. In particular from \cref{yoyo}, XX computes a function ff which is 22n/k2^{\lfloor 2^{n/k} \rfloor}-i.o.α\alpha-e. for some kωk \in \omega.

Using \cref{list_decod}, we pick LωL \in \omega and 0<R<10 \lt R \lt 1 such that for any nn, there exists a collection CnC_n of 2Rn2^{\lfloor Rn \rfloor} strings of length nn, such that no string σ\s of length nn has a Hamming distance less than θ=1α\theta= 1 - \alpha with more than LL strings of CC. Note that such a collection of strings CnC_n is computable uniformly in nn. Uniformly computable in nn we fix a listing σ0n,σ1n,σ2Rn1n\s_0^n, \s_1^n, \dots \s^n_{2^{\lfloor Rn \rfloor}-1} of the elements of CnC_n.

We define the following XX-computable LL-trace {Tn}nω\{T_n\}_{n \in \omega}: For any nn, TnT_n is the collection of integer ii such that the hamming distance between [f(n)][f(n)] and σi2n/k\s_i^{\lfloor 2^{n/k} \rfloor} is less than 1α1 - \alpha. Note that each TnT_n is XX-computable uniformly in nn and that TnL|T_n| \leq L (possibly TnT_n is also empty). Note also that the values of TnT_n are bounded by 2R2n/k2^{\lfloor R2^{n/k} \rfloor}.

We claim that every computable function g<2R2n/kg \lt 2^{\lfloor R2^{n/k} \rfloor} is traced by TnT_n. Indeed, given such a computable function gg, consider the computable function gg' defined by g(n)=σi2n/kg'(n) = \s_i^{\lfloor 2^{n/k} \rfloor} if g(n)=ig(n) = i. We have that gg' is computable, and furthermore g(n)22n/kg'(n) \leq 2^{\lfloor 2^{n/k} \rfloor}. As ff is 22n/k2^{\lfloor 2^{n/k} \rfloor}-i.o.α\alpha-e., there exist infinitely many mm such that d([f(m)],[g(m)])<1αd([f(m)], [g'(m)]) \lt 1 - \alpha. Then, by definition of {Tn}nω\{T_n\}_{n \in \omega}, we have g(m)Tmg(m) \in T_m for each of these mm.

Thus every computable function bounded by 2R2n/k2^{\lfloor R2^{n/k} \rfloor} is captured infinitely often by {Tn}nω\{T_n\}_{n \in \omega}.\\

Now, either the trace T2nT_{2n} must capture infinitely often every computable function bounded by 2R22n/k2^{\lfloor R2^{2n/k} \rfloor}, or the trace T2n+1T_{2n+1} must capture infinitely often every computable function bounded by 2R2(2n+1)/k2^{\lfloor R2^{(2n+1)/k} \rfloor}, as otherwise, by combining the two computable witnesses that neither is the case, we would have a computable function bounded by 2R2n/k2^{\lfloor R2^{n/k} \rfloor} and not traced by {Tn}nω\{T_n\}_{n \in \omega}. In either case, {Tn}nω\{T_n\}_{n \in \omega} can compute a trace which traces every function bounded by 2R22n/k2^{\lfloor R2^{2n/k} \rfloor} (Note that a trace capturing infinitely often every computable function bounded by FF, also captures infinitely often every computable function bounded by G<FG \lt F).

By iterating this argument, XX can compute an LL-trace {Tn}nω\{T_n\}_{n \in \omega} which captures infinitely often every function bounded by 2L2n2^{L 2^{n}}. We can also without loss of generality assume that each element of each TnT_n is bounded by 2L2n2^{L 2^{n}}, and thus coded on exactly L2nL 2^{n} bits. We now use the fact that TnL|T_n| \leq L for every nn, to compute using TnT_n a function h22nh \leq 2^{2^{n}} which is equal infinitely often to every computable function bounded by 22n2^{2^{n}}.

First for every nn, we add if necessary some elements in TnT_n such that Tn=L|T_n| = L. Then we view each element eie_i of TnT_n as an LL-tuple ei1,,eiL\langle e^1_i, \dots, e^L_i \rangle. Formally eije^j_i is the jj-th block of 2n2^n consecutive bits. Consider LL distinct XX-computable functions h1,,hLh_1, \dots, h_L given by hi(n)=eiih_i(n) = e^i_i where ei=ei1,,eii,,eiLe_i = \langle e^1_i, \dots, e^i_i, \dots, e^L_i \rangle is the ii-th element of TnT_n. We claim that at least one hih_i is 2(2n)2^{(2^n)}-i.o.e. Suppose otherwise, and consider the LL computable functions p1,,pLp_1, \dots, p_L witnessing that. Then the computable function p(n)=p1(n),,pL(n)p(n) = \langle p_1(n), \dots, p_L(n) \rangle is never captured by TnT_n, as the ii-th component of p(n)p(n) (seen as a LL-tuple) is different from the ii-th component of the ii-th element of TnT_n (seen as a LL-tuple). This contradicts our hypothesis. So at least one hih_i is 2(2n)2^{(2^n)}-i.o.e.

Note that hih_i is computable from XX. As in \cite[Thm.\ III.4]{Monin.Nies:15} from hih_i we can compute functions which are 2(an)2^{(a^n)}-i.o.e. for any aωa \in \omega; the binary sequence encoding each of these function have a γ\gamma value 1/a\le 1/a. \end{proof}

Note that all the reductions are tttt. Thus this also solves the Γ\Gamma question in the tttt degrees.


6. Brendle and Nies: Analog for cardinal characteristics of Monin's solution to the $\Gamma$ question

For background and definitions of the characteristics see last year's blog \cite[Section 7]{LogicBlog:15}. In analogy to Monin's post above, we will show that d(p)=d(,2(2n))\frd(p)= \frd(\neq^, \tp{(\tp n)}) and b(p)=b(,2(2n))\frb(p)= \frb(\neq^, \tp{(\tp n)}) for each p(0,1/2)p\in (0,1/2).

For convenience here are the main definitions:

Let RX×YR \subseteq X \times Y be a relation between spaces X,YX,Y (such as Baire space) satisfying $\forall x \; \exists y \; (x R y)andand\forall y \; \exists x \; \neg (x R y).Let. LetS = \{ \langle y,x \rangle \in Y \times X \colon \neg xR y\}$.

\begin{definition} We write

\[ \frd(R) = \min\{|G|:G\subseteq Y \land \, \forall x \in X \, \exists y \in G \, xR y\}.\]

\[ \frb(R) = \frd (S) = \min\{|F|:F\subseteq X \land \, \forall y\in Y \exists x \in F \, \neg xR y\}.\] \end{definition}

We will study d(R)\frd(R) and b(R)\frb(R) for two types of relations RR.

\

\n 1. Let h ⁣:ωωh \colon \omega \to \omega (usually unbounded). Define for xωωx \in {}^\omega\omega and

\n yΠn{0,,h(n)1}y \in \Pi_n \{0, \ldots, h(n)-1\},

\[ x \neq^*_h y \LR \fa^\infty n \, [ x(n) \neq y(n)]. \]

\

\n 2. Let 0p1/20 \le p \le 1/2. Define, for x,yω2x,y \in {}^\omega 2

\[ x \sim_p y \LR \underline \rho (x \lra y) >p, \] where xyx \lra y is the set of nn such that x(n)=y(n)x(n) = y(n), and ρ\underline \rho denotes the lower density: ρ(z)=lim infnzn/n\ul \rho (z) = \liminf_n |z \cap n|/n.

\n It will be helpful to express Definition~ ? for these relations in words.

\

\n d(h)\frd(\neq^*_h) is the least size of a set GG of hh-bounded functions so that for each function xx there is a function yy in GG such that n[x(n)y(n)]\fa^\infty n [ x(n) \neq y(n)]. (Of course it suffices to require this for hh-bounded xx.)

\

\n b(h)\frb(\neq^*_h) is the least size of a set FF of functions such that for each hh-bounded function yy, there is a function xx in FF such that nx(n)=y(n)\ex^\infty n \, x(n) = y(n). (Of course we can require that each function in FF is hh-bounded.)

\ \n d(p)\frd(\sim_p) is the least size of a set GG of bit sequences so that for each sequence xx there is a sequence yy in GG so that ρ(xy)>p\ul \rho (x \lra y) \gt p. \

\n b(p)\frb(\sim_p) is the least size of a set FF of bit sequences such that for each bit sequence yy, there is a sequence xx in FF such that ρ(xy)p\ul \rho (x \lra y) \le p.

\begin{definition} Let hh be a function of the form 2h^2^{\hat h} with h^ ⁣:ωω\hat h \colon \, \omega \to \omega, and let XhX_h be the space of all hh-bounded functions. For such a function we view x(n)x(n) either as a number, or as a binary string of length h^(n)\hat h(n) via the binary expansion with leading zeros allowed. We define Lh ⁣:Xhω2L_h\colon X_h \to {}^\omega 2 by Lh(x)=nx(n)L_h(x) = \prod_n x(n), i.e. the concatenation of these strings. We let Kh ⁣:ω2XhK_h \colon {}^\omega 2 \to X_h be the inverse of LhL_h. \end{definition}

We begin with some preliminary facts of independent interest. On occasion we denote a function λn.f(n)\lambda n. f(n) simply by f(n)f(n). The next lemma amplifies functions without changing the cardinal characteristics.

\begin{lemma} \bi \item[(i)] Let hh be nondecreasing and g(n)=h(2n)g(n) = h(2n). We have d(,h)=d(,g)\frd(\neq^,h) = \frd(\neq^,g) and b(,h)=b(,g)\frb(\neq^,h) = \frb(\neq^,g).

\item [(ii)] For each a,b>1a,b \gt 1 we have d(,2(an))=d(,2(bn))\frd(\neq^,{\tp{(a^n)})}= \frd(\neq^,{\tp{(b^n)}}) and

\n b(,2(an))=b(,2(bn))\frb(\neq^,{\tp{(a^n)})}= \frb(\neq^,{\tp{(b^n)}}). \ei \end{lemma}

\begin{proof} (i) Trivially, hgh \le g implies that d(,h)d(,g)\frd(\neq^,h) \ge \frd(\neq^,g) and b(,h)b(,g)\frb(\neq^,h) \le \frb(\neq^,g). So it suffices to show two inequalities.

\vsps

\n \fbox{d(,h)d(,g)\frd(\neq^,h) \le\frd(\neq^,g):} Let GG be a witness set for d(,g)\frd(\neq^,g). Note that GG is also a witness set for d(,h(2n+1))\frd(\neq^,h(2n+1)). Let G^={p0p1 ⁣:p0,p1G}\hat G= \{p_0 \oplus p_1\colon \, p_0, p_1 \in G \}, where (p0p1)(2m+i)=pi(m)(p_0 \oplus p_1)(2m+i) = p_i(m) for i=0,1i= 0,1. Each function in G^\hat G is bounded by hh. Since GG is infinite, G^=G|\hat G| = |G|. Clearly G^\hat G is a witness set for d(,h)\frd(\neq^*,h).

\vsps

\n \fbox{b(,h)b(,g)\frb(\neq^,h) \ge \frb(\neq^,g):} Let FF be a witness set for b(,h)\frb(\neq^*,h). Let F^\hat F consist of the functions of the form np(2n)n \to p(2n), or of the form np(2n+1)n \to p(2n+1), where pFp \in F. Then F^=F|\hat F| = |F|, and each function in F^\hat F is gg bounded.

Clearly, F^\hat F is a witness set for b(,g)\frb(\neq^*,g): if qq is gg-bounded, then q^\hat q is hh bounded where q^(2n+i)=q(n)\hat q(2n+i) = q(n) for i=0,1i=0,1. Let pFp\in F be such that kp(k)=q^(k)\ex^\infty k \, p(k) = \hat q(k). Let i1i \le 1 be such that infinitely many such kk have parity ii. Then the function np(2n+i)n \to p(2n+i) which is in F^\hat F is as required.

(ii) is immediate from (i) by iteration using that a2i>ba^{2^i} \gt b and b2i>ab^{2^i} \gt a for sufficiently large ii. \end{proof}

\begin{lemma} Let aω{0}a \in \omega - \{0\}. We have d(,2(an))d(1/a)\frd( \neq^*,{\tp{(a^n)}}) \le \frd(1/a) and

\n b(,2(an))b(1/a)\frb( \neq^*,{\tp{(a^n)}}) \ge \frb(1/a).\end{lemma} \begin{proof} Let ImI_m for m2m \ge 2 be the m1m-1-th consecutive interval of length ama^m in ω{0}\omega-\{0\}, i.e.

\[ I_m = \big [\frac{a^m-1}{a-1} , \frac{a^{m+1} -1 } {a-1}\big). \] First let GG be a witness set for d(1/a)\frd(1/a). Let h(n)=2(an)h(n) = \tp{(a^n)}. We show that G^={Kh(y) ⁣:yG}\hat G = \{ K_h(y) \colon \, y \in G \} is a witness set for d(,2(an))\frd( \neq^*,{\tp{(a^n)}}). Otherwise there is a sequence zω2z\in {}^\omega 2 such that for each xωωx \in {}^\omega \omega there are infinitely many mm with x(m)=Kh(z)(m)x(m) = K_h(z)(m). Let yy' be the complement ωz\omega- z of zz, that is 00s and 11s are interchanged. Then for infinitely many mm, Lh(x)(i)y(i)L_h(x) (i) \neq y'(i) for each iImi \in I_m. If we let n=1+maxImn = 1+ \max I_m, the proportion of i<ni \lt n such that Lh(x)(i)=y(i)L_h(x) (i) = y'(i) is therefore at most (am1)/(am+11)(a^m-1) / (a^{m+1}-1), which converges to 1/a1/a as mm \to \infty. This contradicts the choice of GG.

Now let FF be a witness set for b(,h)\frb(\neq^*, h). Let F^={ωLh(x) ⁣:xF}\hat F = \{ \omega - L_h(x) \colon \, x \in F \}. For each y2Ny \in \cantor there is xFx\in F such that nKh(y)(n)=x(n)\ex^\infty n \, K_h(y)(n) = x(n). This implies ρ(yx)1/a\ul \rho (y \lra x') \le 1/a where x=ωLh(x)F^x' = \omega - L_h(x) \in \hat F. Hence F^\hat F is a witness set for b(1/a)\frb(1/a). \end{proof}

\begin{thm} Fix any p(0,1/2)p\in (0,1/2). We have d(p)=d(,2(2n))\frd(p)= \frd(\neq^*, \tp{(\tp n)}) and

\n b(p)=b(,2(2n))\frb(p)= \frb(\neq^*, \tp{(\tp n)}). \end{thm}

\begin{proof} By the two foregoing lemmas we have d(p)d(,2(2n))\frd(p) \ge \frd(\neq^, \tp{(\tp n)}) and b(p)b(,2(2n))\frb(p)\le \frb(\neq^, \tp{(\tp n)}). It remains to show the converse inequalities:

\n d(p)d(,2(2n))\frd(p) \le \frd(\neq^, \tp{(\tp n)}) and b(p)b(,2(2n))\frb(p)\ge \frb(\neq^, \tp{(\tp n)}).

\begin{definition} For strings x,yx,y of length rr, the normalised Hamming distance is defined as the proportion of bits on which x,yx,y disagree, that is, \[ d(x,y) = \frac 1 r |\{ i \colon x(n) (i) \neq y(n)(i) \}| \] \end{definition}

\begin{definition} Let hh be a function of the form 2h^2^{\hat h} with h^ ⁣:ωω\hat h \colon \, \omega \to \omega, and let X=Y=XhX=Y= X_h be the space of hh-bounded functions. Let q(0,1/2)q \in (0, 1/2). We define a relation on X×YX \times Y by \[x \neq^*_{\hat h,q} y \LR \fa^\infty n \, [ d(x(n), y(n)) \ge q] \] namely for a.e. nn the strings x(n)x(n) and y(n)y(n) disagree on a proportion of at least qq of the bits. We will usually write ,h^,q\la \neq^*, \hat h,q \ra for this relation. \end{definition} \begin{claim} For each cωc\in \omega there is kωk \in \omega such that \bc d(q2/c)d,2n/k,q\frd(q- 2/c) \le \frd \la \neq^*, \lfloor \tp{n/k} \rfloor, q\ra, and \ec \bc b(q2/c)b,2n/k,q\frb(q- 2/c) \ge \frb \la \neq^*, \lfloor \tp{n/k} \rfloor, q\ra. \ec \end{claim} \n To see this, let kk be large enough so that 21/k1<12c\tp{1/k}-1 \lt \frac 1 {2c}. Let h^(n)=2n/k\hat h(n) = \lfloor \tp{n/k} \rfloor and h=2h^h = \tp{\hat h}. Write H(n)=rnh^(r)H(n) = \sum_{r\le n} \hat h(r). Given an infinite bit sequence, we refer to the bits with position in an interval [H(n),H(n+1))[H(n), H(n+1)) as Block nn (the first block is Block 0). By Monin's 2016 logic blog entry, for sufficiently large nn, \[ \hat h(n+1) \le \frac 1 c H(n). \] For the inequality involving d\frd, let GG be a witness set for d,h^,q\frd \la \neq^*, \hat h , q\ra. Thus, for each function x<hx \lt h there is a function yGy \in G such that for almost all nn, Lh(x),Lh(y)L_h(x), L_h(y) disagree on a proportion of qq bits of Block nn. Let zz be the complement of Lh(y)L_h(y). Given mm, let nn be such that H(n)m<H(n+1)H(n) \le m \lt H(n+1). Since mH(n)1cH(n)m- H(n) \le \frac 1 c H(n), for large enough mm, Lh(x)L_{ h}(x) and zz agree up to mm on a proportion of at least q1.5/cq - 1.5/c bits. So the set of complements of the Lh(y)L_h(y), yGy \in G, forms a witness set for d(q2/c)\frd(q- 2/c) as required. For the inequality involving b\frb, let FF be a witness set for b(q2/c)\frb(q-2/c). Thus, for each y2Ny \in \cantor there is xFx \in F such that ρ(yx)q2/c\ul \rho(y \lra x) \le q-2/c. Let F^={Kh(1x) ⁣:xF}\hat F = \{K_h(1 -x) \colon \, x \in F \}. We show that F^\hat F is a witness set for b,2n/k,q\frb \la \neq^*, \lfloor \tp{n/k} \rfloor, q\ra.

Give a function y<hy \lt h, let y=Lh(y)y' = L_h(y). There is xFx \in F such that ρ(yx)q2/c\ul {\rho} (y' \lra x) \le q - 2/c, and hence ρ(yx)1q+2/c\ol \rho (y' \lra x' ) \ge 1- q+ 2/c where x=1xx' = 1 -x is the complement and ρ\ol \rho denotes the upper density. Then there are infinitely many mm such that the strings y ⁣my'\uhr m and x ⁣mx'\uhr m agree on a proportion of >q+1/c\gt q+1/c bits. Suppose that H(n)m<H(n+1)H(n) \le m \lt H(n+1) then the contribution of disagreement of Block nn is at most 1/c1/c. So there are infinitely many kk so that in Block kk, yy' and xx' agree on a proportion of more than 1q1-q bits, and hence disagree on a proportion of fewer than qq bits. This shows the claim. As in Monin's entry we use the list decoding capacity theorem from the theory of error-correcting codes. Given qq as above and LωL \in \omega, for each rr there is a ``fairly large" set CC of strings of length rr (the allowed code words) such that for each string, at most LL strings in CC have normalised Hamming distance less than qq from σ\sss. (Hence there is only a small set of strings that could be the error-corrected version of σ\sss.) Given string σ\sss of length rr, let Bq(σ)B_q(\sss) denote an open ball around σ\sss in the normalised Hamming distance, namely, B_q(\sss) = \{ \tau \in {}^r 2 \colon \, \sigma, \tau \text{ disagree on fewer thanqrbits}\} \begin{lemma}[List decoding] Let q(0,1/2)q\in (0,1/2). There are ϵ>0\epsilon \gt 0 and LωL \in \omega such that for each rr, there is a set CC of 2ϵr\tp{\lfloor \epsilon r \rfloor } strings of length rr as follows: \bc σr2[Bq(σ)CL]\forall \sss \in {}^r 2 \, [ | B_q(\sss) \cap C | \le L]. \ec \end{lemma}

For LωL \in \omega, an LL-slalom is a function s ⁣:ωω[L]s\colon \, \omega \to \omega^{[\le L]}, i.e.\ a function that maps natural numbers to sets of natural numbers with a size of at most LL. \begin{definition} Fix a function u ⁣:ωωu \colon \omega \to \omega and LωL \in \omega. Let XX be the space of LL-slaloms ss such that maxs(n)<u(n)\max s(n) \lt u(n) for each nn, and let YY be the set of functions such that y(n)<u(n)y(n) \lt u (n) for each nn. Define a relation on X×YX \times Y by \[s \not \ni^*_{u,L} y \LR \fa^\infty n [s(n) \not \ni y(n)]. \] We will write ̸,u,L\la \not \ni^*, u ,L \ra for this relation. \end{definition}

\begin{claim} Given q<1/2q \lt 1/2, let L,ϵL, \epsilon be as in Lemma~ ?. Fix a nondecreasing function h^\hat h, and let u(n)=2ϵh^(n)u(n)= \tp{\lfloor \epsilon \hat h(n) \rfloor }. We have \[ \frd \la \neq^, \hat h , q\ra \le \frd \la \not \ni^, u,L \ra \text{ and } \frb \la \neq^, \hat h , q\ra \ge \frb \la \not \ni^, u,L \ra. \] \end{claim} For the inequality involving d\frd, let GG be a set of functions bounded by uu such that G<d,h^,q|G| \lt \frd \la \neq^, \hat h , q\ra. We show that GG is not a witness set for the right hand side d̸,u,L\frd \la \not \ni^, u,L \ra.

For each rr of the form h^(n)\hat h(n) choose a set C=CrC= C_r as in Lemma~ ?. Since Cr=2ϵr|C_r| = \tp{\lfloor \epsilon r \rfloor} we may choose a sequence \seq {\sss^r_i}_{i\lt \tp{\lfloor \epsilon r \rfloor}} listing CrC_r without repetitions. For a function y<uy \lt u let y~\wt y be the function given by y~(n)=σy(n)h^(n)\wt y(n)= \sss^{\hat h(n)}_{y(n)}. Thus y~(n)\wt y(n) is a binary string of length h^(n)\hat h(n). Let G~={y~ ⁣:yG}\wt G = \{ \wt y \colon \, y \in G \}. Then G~=G<d,h^,q|\wt G| = |G| \lt \frd \la \neq^*, \hat h , q\ra. So there is a function xx with x(n)h^(n)2x(n) \in {}^{\hat h(n)}2 for each nn such that for each yG^y \in \hat G we have n[d(x(n),y(n))<q]\ex^\infty n \, [d(x(n), y(n)) \lt q]. Let ss be the slalom given by \[ s(n) = \{ i \colon \, d (x(n), \sss^{\hat h(n)}_i )< q \}.\] Note that by the choice of the CrC_r according to Lemma~ ?, ss is an LL-slalom. By the definitions, for each yGy \in G we have n[s(n)y(n)]\ex^\infty n \, [s(n) \ni y(n)]. So GG is not a witness set for d̸,u,L\frd \la \not \ni^*, u,L \ra.

For the inequality involving b\frb, suppose FF is a witness set for b,h^,q\frb \la \neq^*, \hat h , q\ra. That is, for each h=2h^h= \tp{\hat h}-bounded function yy, there is xFx\in F such that

\bc n[d(x(n),y(n)<q]\ex^\infty n \, [ d(x(n), y(n) <q] \ec (as usual we view x(n),y(n)x(n), y(n) as binary strings of length h^(n)\hat h(n)). For xFx\in F let sxs_x be the LL-slalom such that

\bc sx(n)={i<u(n) ⁣:d(σih^(n),x(n))<q}s_x(n) = \{i \lt u(n) \colon \, d(\sss^{\hat h(n)}_i, x(n) )\lt q\}. \ec Let F^={sx ⁣:xF}\hat F = \{s_x \colon \, x \in F\}. Given an uu-bounded function yy, let y(n)=σy(n)h^(n)y'(n) = \sss^{\hat h(n)}_{y(n)}. There is xFx \in F such that d(x(n),y(n)<qd(x(n), y'(n) \lt q for infinitely many nn. This means that y(n)sx(n)y(n) \in s_x(n). Hence F^\hat F is a witness set for b̸,u,L\frb \la \not \ni^*, u,L \ra. This shows the claim.

We next need an amplification tool in the context of slaloms. The proof is almost verbatim the one in Lemma~ ?(i), so we omit it.

\begin{claim} Let LωL \in \omega, let the function uu be nondecreasing and let w(n)=u(2n)w(n) = u(2n). We have d(̸,u,L=d̸,w,L\frd(\la \not \ni^,u, L \ra = \frd\la \not \ni^,w,L\ra and b(̸,u,L=b̸,w,L\frb(\la \not \ni^,u, L \ra = \frb\la \not \ni^,w,L\ra. \end{claim}

Iterating the claim, starting with the function h^(n)=2n/k\hat h(n) = \lfloor \tp{n/k}\rfloor with kk as in Claim~ ?, we obtain that d̸,2h^,L=d̸,2(L2n),L\frd \la \not \ni^,\tp{\hat h}, L \ra= \frd \la \not \ni^,\tp{(L 2^n)}, L \ra, and similarly for b\frb.

It remains to verify the following. \begin{claim} d̸,2(L2n),Ld(,2(2n))\frd \la \not \ni^,\tp{(L 2^n)}, L \ra \le \frd(\neq^, \tp{(\tp n)}) and

\n b̸,2(L2n),Lb(,2(2n))\frb \la \not \ni^,\tp{(L 2^n)}, L \ra \ge \frb(\neq^, \tp{(\tp n)}). \end{claim} Given nn, we write a number k<2(L2n)k\lt \tp{(L \tp n)} in binary with leading zeros if necessary, and so can view kk as a binary string of length L2nL \tp n. We view such a string as consisting of LL consecutive blocks of length 2n\tp n.

For the inequality involving d\frd, let GG be a witness set for d(,2(2n))\frd(\neq^*, \tp{(\tp n)}). For functions y1,,yLy_1, \ldots , y_L such that yi(n)<2(2n)y_i(n) \lt \tp{( \tp n)} for each nn, let (y1,,yL)(y_1, \ldots, y_L) denote the function yy with y(n)<2(L2n)y(n) \lt \tp{(L \tp n)} for each nn such that the ii-th block of y(n)y(n) equals yi(n)y_i(n) for each ii with 1iL1 \le i \le L. Let \bc G^={(y1,,yn) ⁣:y1,,yLG}\hat G = \{ (y_1, \ldots, y_n) \colon \, y_1, \ldots, y_L \in G\}. \ec Since GG is infinite we have G^=G|\hat G| = |G|. We check that G^\hat G is a witness set for the left hand side d̸,2(L2n)\frd \la \not \ni^*,\tp{(L 2^n)}\ra. Given an LL-slalom ss bounded by 2(L2n)\tp{(L \tp n)} we may assume that s(n)s(n) has exactly LL members, and they are binary strings of length L2nL \tp n. For iLi \le L let xi(n)x_i(n) be the ii-th block of the ii-th string in s(n)s(n), so that xi(n)=2n|x_i(n)| = \tp n. Viewing the xix_i as functions bounded by 2(2n)\tp{(\tp n)}, we can choose y1,,yLGy_1, \ldots, y_L \in G such that nxi(n)yi(n)\fa^\infty n \, x_i(n) \neq y_i(n). Let y=(y1,,yn)G^y = (y_1, \ldots, y_n) \in \hat G. Then n[s(n)y(n)]\fa^\infty n \, [s(n) \ni y(n)], as required.

For the inequality involving b\frb let FF be a witness set for b̸,2(L2n)\frb \la \not \ni^*,\tp{(L 2^n)}. That is, FF is a set of LL-slaloms ss such that for each function yy with y(n)<2(L2n)y(n) \lt 2^{(L 2^n)}, there is sFs\in F such that s(n)y(n)s(n) \ni y(n) for infinitely many nn.

Let F^\hat F be the set of functions sis_i, for sFs\in F and i<Li<L, such that si(n)s_i(n) is the ii-th block of the ii-th element of s(n)s(n) (as before we may assume that each string in s(n)s(n) has length L2nL2^n). Now let yy be a given function bounded by 2(2n)2^{(2^n)}. Let yy' be the function bounded by 2(L2n)2^{(L2^n)} such that for each nn, each block of y(n)y'(n) equals y(n)y(n). There is sFs\in F such that s(n)y(n)s(n) \ni y'(n) for infinitely many nn. There is i<Li<L such that , y(n)y'(n) is the ii-th string in s(n)s(n) for infinitely many of these nn, and hence y(n)=si(n)y(n) = s_i(n). Thus F^\hat F is a witness set for b(,2(2n))\frb(\neq^*, \tp{(\tp n)}). This proves the claim.

We can now summarise the argument that d(p)d(,2(2n))\frd(p) \le \frd(\neq^*, \tp{(\tp n)}). Pick cc large enough such that q=p+2/c<1/2q= p+2/c \lt 1/2.

By Claim~ ? there is kk such that \bc d(p)d,2n/k,q\frd(p) \le \frd \la \neq^*, \lfloor \tp{n/k} \rfloor, q\ra. \ec

By Claim~ ? there are LL, ϵ\epsilon such that where h^(n)=2n/k\hat h(n) = \lfloor \tp{n/k} \rfloor, we have \bc d,h^,qd̸,u,L\frd \la \neq^, \hat h , q\ra \le \frd \la \not \ni^, u,L \ra, \ec where u(n)=2ϵh^(n)u(n)= \tp{\lfloor \epsilon \hat h(n) \rfloor }.

Applying Claim~ ? sufficiently many times we have \bc d̸,u,Ld̸,2(L2n),L\frd \la \not \ni^, u,L \ra \le \frd \la \not \ni^, \tp{(L 2^n)} ,L \ra. \ec

\n Finally, d̸,2(L2n),Ld(,2(2n))\frd \la \not \ni^,\tp{(L 2^n)}, L \ra \le \frd(\neq^, \tp{(\tp n)}) by Claim~ ?. The argument for b(p)b(,2(2n))\frb(p)\ge \frb(\neq^*, \tp{(\tp n)}) is the exact dual. \end{proof}


7. Nies: answering the $\Delta$ question

We use the notation in 5. Let RX×YR \subseteq X \times Y be a relation between spaces X,YX,Y, and let S={y,xY×X ⁣:¬xRy}S = \{ \langle y,x \rangle \in Y \times X \colon \neg xR y\}. Suppose we have specified what it means for objects xx in XX, yy in YY to be computable in a Turing oracle AA. We denote this by for example xTAx\leT A. In particular, for A=A= \emptyset we have a notion of computable objects.

Let the variable xx range over XX, and let yy range over YY. We define the highness properties

\[ \+ B(R) = \{ A: \,\exists y \leT A \, \fa x \ \text{computable} \ [xRy] \} \]

\[ \+ D(R) = \+ B(S) = \{ A: \,\exists x \leT A \, \fa y \ \text{computable} \ [\neg xRy] \} \]

\n 1. Let h ⁣:ωω{0,1}h \colon \omega \to \omega - \{0,1\}. Define for xωωx \in {}^\omega\omega and

\n yn{0,,h(n)1}ωωy \in \prod_n \{0, \ldots, h(n)-1\} \sub {}^\omega\omega,

\[ x \neq^*_h y \LR \fa^\infty n \, [ x(n) \neq y(n)]. \]

\n 2. Let 0p1/20 \le p \le 1/2. Define, for x,yω2x,y \in {}^\omega 2

\[ x \sim_p y \LR \underline \rho (x \lra y) >p, \] where xyx \lra y is the set of nn such that x(n)=y(n)x(n) = y(n), and ρ\underline \rho denotes the lower density: ρ(z)=lim infnzn/n\ul \rho (z) = \liminf_n |z \cap n|/n.

It may be helpful to separately state two special cases. \begin{definition} For a computable function hh, we let \+B(h)\+ B(\neq^*_h) denote the class of oracles AA that compute a function y<hy \lt h such that for each computable function xx, we have nx(n)y(n)\fa^\infty n \, x(n) \neq y(n).

For p<1/2p\lt 1/2, we let \+B(p)\+ B(\sim_p), or \+B(p)\+ B(p) for short, denote the class of oracles AA that compute a set yy such that for each computable set xx, we have ρ(xy)>p\ul \rho (x \lra y) \gt p. \end{definition}

Recall Definition~ ? and that for each pp with 0p<1/20 \le p \lt 1/2, \bc Δ(A)>pA\+B(p)Δ(A)p\Delta(A) \gt p \RA A \in \+ B(\sim_p) \RA \Delta(A) \ge p. \ec

We show that \+B(p)=\+B(,2(2n))\+ B(\sim_p)= \+ B(\neq^*, \tp{(\tp n)}) for each p(0,1/2)p\in (0,1/2). In particular, Δ(A)>0Δ(A)=1/2\Delta(A) \gt 0 \RA \Delta(A) = 1/2 so there are only two possible Δ\Delta values.

We begin with some preliminary facts of independent interest. On occasion we denote a function λn.f(n)\lambda n. f(n) simply by f(n)f(n). \begin{lemma} \bi \item[(i)] Let hh be nondecreasing and g(n)=h(2n)g(n) = h(2n). We have \+B(,h)=\+B(,g)\+ B(\neq^,h) = \+ B(\neq^,g).

\item [(ii)] For each a,b>1a,b \gt 1 we have \+B(,2(an))=\+B(,2(bn))\+ B(\neq^,{\tp{(a^n)})}= \+ B(\neq^,{\tp{(b^n)}}). \ei \end{lemma}

\begin{proof} (i) Trivially, hgh \le g implies that \+B(,h)\+B(,g)\+ B(\neq^,h) \sub \+ B(\neq^,g). So it suffices to show the converse inclusion \+B(,h)\+B(,g)\+ B(\neq^,h) \supseteq \+ B(\neq^,g).

Let yTAy\leT A, y<gy \lt g be a function witnessing that AB(,g)A \in B(\neq^,g). Let y^(2n+i)=y(n)\hat y(2n+i) = y(n) for i1i \le 1, so that y^<h\hat y \lt h. Given any computable function xx, for almost every nn we have x(2n)y(n)x(2n) \neq y(n) and x(2n+1)y(n)x(2n+1) \neq y(n). Therefore n[x(n)y^(n)]\fa^\infty n \, [ x(n) \neq \hat y(n)]. Hence y^\hat y is a witness for AB(,h)A \in B(\neq^,h).

(ii) is immediate from (i) by iteration using that a2i>ba^{2^i} \gt b and b2i>ab^{2^i} \gt a for sufficiently large ii. \end{proof}

Recall Def.\ ? of the LhL_h and KhK_h operators. \begin{lemma} Let aω{0}a \in \omega - \{0\}. We have \+B(,2(an))\+B(1/a)\+ B( \neq^*,{\tp{(a^n)}}) \supseteq \+ B(1/a). \end{lemma} \begin{proof} Let ImI_m for m2m \ge 2 be the m1m-1-th consecutive interval of length ama^m in ω{0}\omega-\{0\}, i.e.

\[ I_m = \big [\frac{a^m-1}{a-1} , \frac{a^{m+1} -1 } {a-1}\big). \] Let h(m)=2amh(m) = \tp{a^m}. Let yTAy \leT A witness that A\+B(1/a)A \in \+ B(1/a), and let y^=Kh(y)\hat y = K_h(y). Given a computable function x<hx \lt h, let x=1Lh(x)x' = 1- L_h(x). Since ρ(xy)>1/a\ul \rho( x' \lra y) \gt 1/a, for large enough nn, there is kInk \in I_n such that x(i)=y(i)x'(i) = y(i). Hence we cannot have x(n)=y^(n)x(n) = \hat y(n). Thus y^\hat y witnesses that A\+B(,2(an))A \in \+ B( \neq^*,{\tp{(a^n)}}). \end{proof}

A similar argument shows that \+B(,2h^(m))\+B(0)\+ B( \neq^*,{\tp{\hat h(m)}}) \supseteq \+ B(0) for any computable function h^\hat h such that amh^(m)am\fa a \fa^\infty m \, \hat h(m) \ge a^m. Now the mm-th interval has length h^(m)\hat h (m).

\begin{thm} Fix any p(0,1/2)p\in (0,1/2). We have \+B(p)=\+B(,2(2n))\+ B(p)= \+ B(\neq^*, \tp{(\tp n)}). \end{thm}

\begin{proof} The two foregoing lemmas imply \+B(p)\+B(,2(2n))\+ B(p)\sub \+ B(\neq^, \tp{(\tp n)}). It remains to show the converse inclusion \+B(p)\+B(,2(2n))\+ B(p)\supseteq \+ B(\neq^, \tp{(\tp n)}).

\begin{definition} For strings x,yx,y of length rr, the normalised Hamming distance is defined as the proportion of bits on which x,yx,y disagree, that is, \[ d(x,y) = \frac 1 r |\{ i \colon x(n) (i) \neq y(n)(i) \}| \] \end{definition}

\begin{definition} Let hh be a function of the form 2h^2^{\hat h} with h^ ⁣:ωω\hat h \colon \, \omega \to \omega, and let X=Y=XhX=Y= X_h be the space of hh-bounded functions. Let q(0,1/2)q \in (0, 1/2). We define a relation on X×YX \times Y by \[x \neq^*_{\hat h,q} y \LR \fa^\infty n \, [ d(x(n), y(n)) \ge q] \] namely for a.e. nn the strings x(n)x(n) and y(n)y(n) disagree on a proportion of at least qq of the bits. We will usually write ,h^,q\la \neq^*, \hat h,q \ra for this relation. \end{definition} The first step makes the crucial transition from the density setting to the combinatorial setting. \begin{claim} Let q(0,1/2)q \in (0, 1/2). For each cωc\in \omega such that 2/c<q2/c<q, there is kωk \in \omega such that \bc \+B(q2/c)\+B,2n/k,q\+ B(q- 2/c) \supseteq \+ B \la \neq^*, \lfloor \tp{n/k} \rfloor, q\ra. \ec \end{claim} \n To see this, let kk be large enough so that 21/k1<12c\tp{1/k}-1 \lt \frac 1 {2c}. Let h^(n)=2n/k\hat h(n) = \lfloor \tp{n/k} \rfloor and h=2h^h = \tp{\hat h}. Write H(n)=rnh^(r)H(n) = \sum_{r\le n} \hat h(r). Given an infinite bit sequence, we refer to the bits with position in an interval [H(n),H(n+1))[H(n), H(n+1)) as Block nn (the first block is Block 0). By Monin's 2016 logic blog entry, for sufficiently large nn, \[ \hat h(n+1) \le \frac 1 c H(n). \] Let yTAy \leT A be a witness for A\+B,2n/k,qA \in \+ B \la \neq^*, \lfloor \tp{n/k} \rfloor, q\ra. Thus, y<hy\lt h and n[d(Lh(x)(n),Lh(y)(n)q]\fa^\infty n \, [d(L_h(x)(n), L_h(y)(n) \ge q]. Let y=1Lh(y)y' = 1 - L_h(y). Then \bc n[d(x(n),y(n))<q]\fa^\infty n \, [d(x'(n), y'(n) )\lt q] \ec for each computable x2Nx' \in \cantor. Suppose that H(n)m<H(n+1)H(n) \le m \lt H(n+1). Then the contribution of Block nn to the proportion of disagreement between x,yx', y' is at most 1/c1/c. So ρ(yx)>q2/c\ul \rho (y' \lra x') \gt q-2/c. Hence yTAy'\leT A is a witness for A\+B(q2/c)A\in \+ B(q-2/c). This shows the claim.

For LωL \in \omega, an LL-slalom is a function s ⁣:ωω[L]s\colon \, \omega \to \omega^{[\le L]}, i.e.\ a function that maps natural numbers to sets of natural numbers with a size of at most LL. \begin{definition} Fix a function u ⁣:ωωu \colon \omega \to \omega and LωL \in \omega. Let XX be the space of LL-slaloms (or traces) ss such that maxs(n)<u(n)\max s(n) \lt u(n) for each nn. Thus ss maps natural numbers to sets of natural numbers of size at most LL, represented by strong indices. Let YY be the set of functions such that y(n)<u(n)y(n) \lt u (n) for each nn. Define a relation on X×YX \times Y by \[s \not \ni^*_{u,L} y \LR \fa^\infty n [s(n) \not \ni y(n)]. \] We will write ̸,u,L\la \not \ni^*, u ,L \ra for this relation. \end{definition}

\begin{claim} Given q<1/2q \lt 1/2, let L,ϵL, \epsilon be as in Lemma~ ?. Fix a nondecreasing computable function h^\hat h, and let u(n)=2ϵh^(n)u(n)= \tp{\lfloor \epsilon \hat h(n) \rfloor }. We have \bc \+B,h^,q\+B̸,u,L\+ B \la \neq^, \hat h , q\ra \supseteq \+ B \la \not \ni^, u,L \ra. \ec \end{claim}

For each rr of the form h^(n)\hat h(n) compute a set C=CrC= C_r as in Lemma~ ?. Since Cr=2ϵr|C_r| = \tp{\lfloor \epsilon r \rfloor} there is a uniformly computable sequence \seq {\sss^r_i}_{i\lt \tp{\lfloor \epsilon r \rfloor}} listing CrC_r in increasing lexicographical order.

Suppose that yTAy \leT A is a witness for A\+B̸,u,LA \in \+ B \la \not \ni^*, u,L \ra. Let y~<h\wt y \lt h be the function given by y~(n)=σy(n)h^(n)\wt y(n)= \sss^{\hat h(n)}_{y(n)}. We show that y~\wt y is a witness for

\n A\+B,h^,qA\in \+ B \la \neq^*, \hat h , q\ra.

For a computable function x<hx \lt h, let sxs_x be the computable LL-trace such that

\bc sx(n)={i<u(n) ⁣:d(σih^(n),x(n))<q}s_x(n) = \{i \lt u(n) \colon \, d(\sss^{\hat h(n)}_i, x(n) )\lt q\}. \ec Since yy is a witness for A\+B̸,u,LA \in \+ B \la \not \ni^*, u,L \ra, for almost every nn we have y(n)∉sx(n)y(n) \not \in s_x(n). Hence d(y~(n),x(n)qd(\wt y(n),x(n) \ge q, as required.

We next need an amplification tool in the context of traces. The proof is almost verbatim the one in Lemma~ ?(i), so we omit it.

\begin{claim} Let LωL \in \omega, let the computable function uu be nondecreasing and let w(n)=u(2n)w(n) = u(2n). We have \+B(̸,u,L=\+B̸,w,L\+ B(\la \not \ni^,u, L \ra = \+ B\la \not \ni^,w,L\ra. \end{claim}

Iterating the claim, starting with the function h^(n)=2n/k\hat h(n) = \lfloor \tp{n/k}\rfloor with kk as in Claim~ ?, we obtain that \+B̸,2h^,L=\+B̸,2(L2n),L\+ B\la \not \ni^,\tp{\hat h}, L \ra= \+ B \la \not \ni^,\tp{(L 2^n)}, L \ra.

It remains to verify the following, which would work for any computable function h^(n)\hat h(n) in place of the 2n2^n in the exponents. \begin{claim} \+B̸,2(L2n),L\+B(,2(2n))\+ B \la \not \ni^,\tp{(L 2^n)}, L \ra \supseteq \+ B(\neq^, \tp{(\tp n)}). \end{claim} Given nn, we write a number k<2(L2n)k\lt \tp{(L \tp n)} in binary with leading zeros if necessary, and so can view kk as a binary string of length L2nL \tp n. We view such a string as consisting of LL consecutive blocks of length 2n\tp n.

Let yy be a witness function for \+B(,2(2n))\+ B(\neq^*, \tp{(\tp n)}). That is, y<2(2n)y\lt 2^{(2^n)} and nx(n)y(n)\fa^\infty n \, x(n) \neq y(n) for each computable function xx. Let yy' be the function bounded by 2(L2n)2^{(L2^n)} such that for each nn, each block of y(n)y'(n) equals y(n)y(n). Given a computable LL-trace ss with maxs(n)<2(L2n)\max s(n) \lt \tp{(L 2^n)}, for i<Li\lt L let xix_i be the computable function such that xi(n)x_i(n) is the ii-th block of the ii-th element of s(n)s(n) (as before we may assume that each string in s(n)s(n) has length L2nL2^n). For sufficiently large nn, we have i<Ly(n)xi(n)\fa i \lt L \, y(n) \neq x_i(n). Hence ns(n)∌y(n)\fa^\infty n \, s(n) \not \ni y'(n) and yy' is a witness for A\+B̸,2(L2n)A\in \+ B \la \not \ni^*,\tp{(L 2^n)}.

We can now summarise the argument that \+B(p)\+B(,2(2n))\+ B(p) \supseteq \+ B(\neq^*, \tp{(\tp n)}). Pick cc large enough such that q=p+2/c<1/2q= p+2/c \lt 1/2.

By Claim~ ? there is kk such that \bc \+B(p)\+B,2n/k,q\+ B(p) \supseteq\+ B \la \neq^*, \lfloor \tp{n/k} \rfloor, q\ra. \ec

By Claim~ ? there are LL, ϵ\epsilon such that where h^(n)=2n/k\hat h(n) = \lfloor \tp{n/k} \rfloor and u(n)=2ϵh^(n)u(n)= \tp{\lfloor \epsilon \hat h(n) \rfloor }, we have \bc \+B,h^,q\+B̸,u,L\+ B \la \neq^, \hat h , q\ra \supseteq\+ B \la \not \ni^, u,L \ra. \ec

Applying Claim~ ? sufficiently many times we have \bc \+B̸,u,L\+B̸,2(L2n),L\+ B \la \not \ni^, u,L \ra \supseteq\+ B \la \not \ni^, \tp{(L 2^n)} ,L \ra. \ec

\n Finally, \+B̸,2(L2n),L\+B(,2(2n))\+ B \la \not \ni^,\tp{(L 2^n)}, L \ra \supseteq\+ B(\neq^, \tp{(\tp n)}) by Claim~ ?. \end{proof} We note that by the proofs, both inclusions in Theorem~ ? are uniform in a strong sense: from a witness yTAy \leT A for one property one can compute a witness yy' for the other property.

As a corollary to Theorem~ ? we obtain a proof of Proposition~ ?. If AA is 2-generic then AA is neither high nor d.n.c., so AA is not in \+B()=high or d.n.c.\+ B(\neq^) = \text{high or d.n.c.} the class where no bound is imposed on the witness function AA computes. So AA is not in B(,2(2n))B(\neq^, \tp{(\tp n)}), hence Δ(A)=0\Delta(A)=0.

\part{Reverse mathematics}


8. Belanger, Nies and Shafer: the strength of randomness existence axioms

David Belanger, Andr\'e Nies and Paul Shafer others discussed the strength of randomness existence axioms at NUS and University of Ghent in February/March. In \cite[Section.\ 9]{LogicBlog:13}, for a randomness notion \+C\+ C, we defined \+C0\+ C_0 to be the system RCA+XYY\+CX\mathtt{RCA} + \fa X \ex Y \, Y \in \+ C^X. For instance, \MLR_0 is equivalent to weak weak K\"onigs Lemma over RCA\mathtt{RCA}. The system CR0\mathtt{CR}_0 (computable randomness) appears to be equivalent to the seemingly weaker SR0\mathtt{SR}_0 (Schnorr randomness) (\cite[Prop.\ 9.2]{LogicBlog:13}; the strength of induction axioms that are needed to show this remains to be checked carefully).

2-randomness versus weak 2-randomness

On the other hand 2R0\twoR_0 (the system for 2-randomness) is strictly stronger than

W2R0\WtwoR_0 (the system for weak 2 randomness). To see this, take a weakly 2-random ZZ that does not compute a 2-random. For instance, any 2-random has hyperimmune degree. Any computably dominated ML-random ZZ is weakly 2-random and hence does not compute a 2-random. For each nn let ZnZ_n be the nn-th column of ZZ, that is, Zn={k ⁣:k,nZ}Z_n = \{ k \colon \, \la k,n \ra \in Z\}. Let \+M=(N,\+S)\+ M = ( \NN, \+ S) where \+S\+ S consists of all the sets Turing below the join of finitely many columns of ZZ. Note that ZnZ_n is weakly 2-random in any finite sum of columns not containing ZnZ_n. So \+M\+ M is a model of W2R0\WtwoR_0. We can also separate the two randomness existence axioms via an interesting mathematical consequence: Csima and Mileti~8 have shown that 2R0\twoR_0 implies the Rainsey Rambo's theorem. \begin{prop} W2R0\WtwoR_0 does not imply the Rainbow Ramsey's theorem. \end{prop} \begin{proof} Joseph Miller has shown that the Rainbow Ramsey's theorem is equivalent over RCA0\mathtt{RCA}_0 plus some induction to the existence of a d.n.c.\ function relative to \Halt. (Detail needed here on the construction for the forward direction: recursive in a homogeneous set we obtain the function.) By \cite[Exercise 4.3.18]{Nies:book} there is a weakly 2-random set ZZ that does not compute a 2-fixed point free function, and hence it computes no d.n.c.\ function relative to \Halt. Construct the model \+MW2R0\+ M \models \WtwoR_0 from ZZ as above. Then Rainbow Ramsey's theorem fails in \+M\+ M. \end{proof}

Weak Demuth randomness versus \mathtt{WKL} \begin{definition} A Δ20\DII function ff is ω\w-c.e.\ if there is a computable function hh such that h(n)h(n) bounds the number of changes in a computable approximation to f(n)f(n). A Demuth test is an effective sequence \seq{\+ U_n} of effectively open (Σ10\Sigma^0_1) subsets of Cantor space such that: 1. For all nn, the measure λ(\+Un)\lambda (\+ U_n) of \+Un\+ U_n is bounded by 2n2^{-n}; and 2. there is an ω\w-c.e.\ function mapping nn to a Σ10\Sigma^0_1 index for \+Un\+ U_n. A set (an element of Cantor space) XX is captured by a Demuth test \seq{\+ U_n} if X\+UnX\in \+ U_n for infinitely many nn. A set is Demuth random if it is not captured by any Demuth test. A set ZZ weakly passes a test \seq{\+ U_n} if Z∉n\+UnZ \not \in \bigcap_n \+ U_n. A set ZZ is weakly Demuth random if it weakly passes every Demuth test.

\end{definition} Figueira et al.\ 13 introduced balanced randomness, a notion in between weak Demuth randomness and ML-randomness where the mm-th test component \+Um\+ U_m of a test can be ``replaced" at most O(2m)O(2^m) times. This notion is still stronger than Oberwolfach randomness. More generally, for an order function hh we say that ZZ is hh- weak Demuth random if it weakly passes each Demuth test where the component \+Um\+ U_m can be replaced at most h(m)h(m) times. It was observed in 3 that the methods of 13 show the following. \begin{prop} Let Z=Z0Z1Z= Z_0 \oplus Z_1 be ML-random. Then Z0Z_0 or Z1Z_1 is balanced random, and in fact O(r(n)2n)O(r(n)2^{n})-weak Demuth random for some order function rr. \end{prop} \begin{proof} We use the terminology of 13. If Z0Z_0 is ω\omega-c.e.\ tracing then any weak Demuth test (which is given by an ω\omega-c.e.\ function) can be converted into a ML-test relative to Z0Z_0. So by van Lambalgen theorem, Z1Z_1 is weak Demuth random. If Z0Z_0 is not ω\omega-c.e.\ tracing then by \cite[Thm.\ 23]{Figueira.Hirschfeldt.ea:15} Z0Z_0 is O(r(n)2n)O(r(n)2^{n})-weak Demuth random for some order function rr, and in particular, balanced random. \end{proof} So weak weak K\"onigs lemma plus sufficient induction implies the axiom for balanced randomness. \begin{definition} For a computable function hh, we say that a set ZZ is hh-c.e.\ if there is a computable approximation such that Z ⁣nZ\uhr n changes at most h(n)h(n) times. For instance, each left-c.e.\ set is 2n2^n-c.e. \end{definition} Such a set is clearly not hh-weak Demuth random. So the following ω\omega-model \+M\+ M satisfies WKL\mathtt{WKL} but not the axiom for weak hh-Demuth randomness, for any function hh that dominates each function λn.kn\lambda n . k^n , such as h(n)=2np(n)h(n) = 2^{n \cdot p(n)} for some order function pp.

\begin{prop} There is an ω\omega-model \+M\+ M of WKL\mathtt{WKL} such that each set of \+M\+ M is superlow and knk^n-c.e.\ for some kNk \in \NN. \end{prop} \begin{proof} Let \+S(X)\+ S(X) be the Π10\PPI class relative to XX of sets that are PA-complete in XX. Over RCA\mathtt{RCA}, the axiom WKL\mathtt{WKL} is equivalent to X\+S(X)\fa X \, \+ S(X) \neq \ES. Let \+Q\+ Q be the Π10\PPI class consisting of the sets YY such that Yi+1\+S(kiYk)Y_{i+1} \in \+ S({\bigoplus_{k \le i} Y_k}) for each ii; here Yi={n ⁣:i,nY}Y_i = \{ n \colon \, \la i,n\ra \in Y\} is the ii-th column of YY. If Y\+QY \in \+ Q then the Turing ideal generated by the columns of YY determines an ω\omega-model \+M\+ M of WKL\mathtt{WKL}. Let XWXX \to W^X be the c.e.\ operator such that \bc 2e(2n+1)WXΦeX(n)=1}2^e (2n+1) \in W^X \LR \Phi_e^X(n) = 1\}. \ec By the superlow basis theorem as stated in \cite[1.8.38]{Nies:book}, but with the operator WW instead of the domain of the usual Turing jump JJ, there is Y\+QY \in \+ Q such that WYW^Y is left-c.e. Suppose that R=ΦeYR = \Phi_e^Y. Since WYW^Y is left-c.e., RR is 22e(2n+1)2^{2^e (2n+1)}-c.e., and hence knk^n-c.e. where k=22e+2k= 2^{2^{e+2}}. Thus each set of \+M\+ M is knk^n-c.e.\ for some kNk \in \NN. Clearly YmWYY' \le_m W^Y. So YY is superlow. \end{proof}


9. Belanger, Nies and Shafer: the strength of randomness existence axioms

David Belanger, Andr\'e Nies and Paul Shafer others discussed the strength of randomness existence axioms at NUS and University of Ghent in February/March. In \cite[Section.\ 9]{LogicBlog:13}, for a randomness notion \+C\+ C, we defined \+C0\+ C_0 to be the system RCA+XYY\+CX\mathtt{RCA} + \fa X \ex Y \, Y \in \+ C^X. For instance, \MLR_0 is equivalent to weak weak K\"onigs Lemma over RCA\mathtt{RCA}. The system CR0\mathtt{CR}_0 (computable randomness) appears to be equivalent to the seemingly weaker SR0\mathtt{SR}_0 (Schnorr randomness) (\cite[Prop.\ 9.2]{LogicBlog:13}; the strength of induction axioms that are needed to show this remains to be checked carefully).

2-randomness versus weak 2-randomness

On the other hand 2R0\twoR_0 (the system for 2-randomness) is strictly stronger than

W2R0\WtwoR_0 (the system for weak 2 randomness). To see this, take a weakly 2-random ZZ that does not compute a 2-random. For instance, any 2-random has hyperimmune degree. Any computably dominated ML-random ZZ is weakly 2-random and hence does not compute a 2-random. For each nn let ZnZ_n be the nn-th column of ZZ, that is, Zn={k ⁣:k,nZ}Z_n = \{ k \colon \, \la k,n \ra \in Z\}. Let \+M=(N,\+S)\+ M = ( \NN, \+ S) where \+S\+ S consists of all the sets Turing below the join of finitely many columns of ZZ. Note that ZnZ_n is weakly 2-random in any finite sum of columns not containing ZnZ_n. So \+M\+ M is a model of W2R0\WtwoR_0. We can also separate the two randomness existence axioms via an interesting mathematical consequence: Csima and Mileti~8 have shown that 2R0\twoR_0 implies the Rainsey Rambo's theorem. \begin{prop} W2R0\WtwoR_0 does not imply the Rainbow Ramsey's theorem. \end{prop} \begin{proof} Joseph Miller has shown that the Rainbow Ramsey's theorem is equivalent over RCA0\mathtt{RCA}_0 plus some induction to the existence of a d.n.c.\ function relative to \Halt. (Detail needed here on the construction for the forward direction: recursive in a homogeneous set we obtain the function.) By \cite[Exercise 4.3.18]{Nies:book} there is a weakly 2-random set ZZ that does not compute a 2-fixed point free function, and hence it computes no d.n.c.\ function relative to \Halt. Construct the model \+MW2R0\+ M \models \WtwoR_0 from ZZ as above. Then Rainbow Ramsey's theorem fails in \+M\+ M. \end{proof}

Weak Demuth randomness versus \mathtt{WKL} \begin{definition} A Δ20\DII function ff is ω\w-c.e.\ if there is a computable function hh such that h(n)h(n) bounds the number of changes in a computable approximation to f(n)f(n). A Demuth test is an effective sequence \seq{\+ U_n} of effectively open (Σ10\Sigma^0_1) subsets of Cantor space such that: 1. For all nn, the measure λ(\+Un)\lambda (\+ U_n) of \+Un\+ U_n is bounded by 2n2^{-n}; and 2. there is an ω\w-c.e.\ function mapping nn to a Σ10\Sigma^0_1 index for \+Un\+ U_n. A set (an element of Cantor space) XX is captured by a Demuth test \seq{\+ U_n} if X\+UnX\in \+ U_n for infinitely many nn. A set is Demuth random if it is not captured by any Demuth test. A set ZZ weakly passes a test \seq{\+ U_n} if Z∉n\+UnZ \not \in \bigcap_n \+ U_n. A set ZZ is weakly Demuth random if it weakly passes every Demuth test.

\end{definition} Figueira et al.\ 13 introduced balanced randomness, a notion in between weak Demuth randomness and ML-randomness where the mm-th test component \+Um\+ U_m of a test can be ``replaced" at most O(2m)O(2^m) times. This notion is still stronger than Oberwolfach randomness. More generally, for an order function hh we say that ZZ is hh- weak Demuth random if it weakly passes each Demuth test where the component \+Um\+ U_m can be replaced at most h(m)h(m) times. It was observed in 3 that the methods of 13 show the following. \begin{prop} Let Z=Z0Z1Z= Z_0 \oplus Z_1 be ML-random. Then Z0Z_0 or Z1Z_1 is balanced random, and in fact O(r(n)2n)O(r(n)2^{n})-weak Demuth random for some order function rr. \end{prop} \begin{proof} We use the terminology of 13. If Z0Z_0 is ω\omega-c.e.\ tracing then any weak Demuth test (which is given by an ω\omega-c.e.\ function) can be converted into a ML-test relative to Z0Z_0. So by van Lambalgen theorem, Z1Z_1 is weak Demuth random. If Z0Z_0 is not ω\omega-c.e.\ tracing then by \cite[Thm.\ 23]{Figueira.Hirschfeldt.ea:15} Z0Z_0 is O(r(n)2n)O(r(n)2^{n})-weak Demuth random for some order function rr, and in particular, balanced random. \end{proof} So weak weak K\"onigs lemma plus sufficient induction implies the axiom for balanced randomness. \begin{definition} For a computable function hh, we say that a set ZZ is hh-c.e.\ if there is a computable approximation such that Z ⁣nZ\uhr n changes at most h(n)h(n) times. For instance, each left-c.e.\ set is 2n2^n-c.e. \end{definition} Such a set is clearly not hh-weak Demuth random. So the following ω\omega-model \+M\+ M satisfies WKL\mathtt{WKL} but not the axiom for weak hh-Demuth randomness, for any function hh that dominates each function λn.kn\lambda n . k^n , such as h(n)=2np(n)h(n) = 2^{n \cdot p(n)} for some order function pp.

\begin{prop} There is an ω\omega-model \+M\+ M of WKL\mathtt{WKL} such that each set of \+M\+ M is superlow and knk^n-c.e.\ for some kNk \in \NN. \end{prop} \begin{proof} Let \+S(X)\+ S(X) be the Π10\PPI class relative to XX of sets that are PA-complete in XX. Over RCA\mathtt{RCA}, the axiom WKL\mathtt{WKL} is equivalent to X\+S(X)\fa X \, \+ S(X) \neq \ES. Let \+Q\+ Q be the Π10\PPI class consisting of the sets YY such that Yi+1\+S(kiYk)Y_{i+1} \in \+ S({\bigoplus_{k \le i} Y_k}) for each ii; here Yi={n ⁣:i,nY}Y_i = \{ n \colon \, \la i,n\ra \in Y\} is the ii-th column of YY. If Y\+QY \in \+ Q then the Turing ideal generated by the columns of YY determines an ω\omega-model \+M\+ M of WKL\mathtt{WKL}. Let XWXX \to W^X be the c.e.\ operator such that \bc 2e(2n+1)WXΦeX(n)=1}2^e (2n+1) \in W^X \LR \Phi_e^X(n) = 1\}. \ec By the superlow basis theorem as stated in \cite[1.8.38]{Nies:book}, but with the operator WW instead of the domain of the usual Turing jump JJ, there is Y\+QY \in \+ Q such that WYW^Y is left-c.e. Suppose that R=ΦeYR = \Phi_e^Y. Since WYW^Y is left-c.e., RR is 22e(2n+1)2^{2^e (2n+1)}-c.e., and hence knk^n-c.e. where k=22e+2k= 2^{2^{e+2}}. Thus each set of \+M\+ M is knk^n-c.e.\ for some kNk \in \NN. Clearly YmWYY' \le_m W^Y. So YY is superlow. \end{proof}


10. Carlucci: Bounded Hindman's Theorem and Increasing Polarized Ramsey's Theorem

The following results were proved after reading the paper Effectiveness of Hindman's Theorem for bounded sums by Dzhafarov, Jockusch, Solomon and Westrick, 10.

The following natural restriction of Hindman's Theorem to sums with a bounded number of terms was discussed by Blass in 4 and first studied from a Reverse Mathematics perspective by Dzhafarov et alii in 10.

\begin{definition}[Hindman's Theorem with bounded sums] HTkn\mathsf{HT}^{\leq n}_k states that for every coloring f:Nkf:\mathbb{N}\rightarrow k there exists an infinite set HH such that FSn(H)FS^{\leq n}(H) is monochromatic for ff, where FSn(H)FS^{\leq n}(H) denotes the set of all finite sums of at most nn distinct members of HH. We denote k HTkn\forall k \ \mathsf{HT}^{\leq n}_k by HTn\mathsf{HT}^{\leq n}. \end{definition}

The main results in 10 are (1) that HT22\mathsf{HT}^{\leq 2}_2 is unprovable in RCA0\mathsf{RCA}_0 and (2) that HT33\mathsf{HT}^{\leq 3}_3 proves ACA0\mathsf{ACA}_0 over RCA0\mathsf{RCA}_0.

\bigskip The following version of Ramsey's Theorem is introduced in 9.

\begin{definition}[Increasing Polarized Ramsey Theorem] IPTkn\mathsf{IPT}^n_k is the following principle: for every f:[N]nkf:[\mathbb{N}]^n\rightarrow k there exists a sequence H1,,Hn\langle H_1,\dots,H_n\rangle of infinite sets and c<kc \lt k such that for all increasing tuple (x1,,xn)H1××Hn(x_1,\dots,x_n)\in H_1\times\dots\times H_n we have f(x1,,xn)=cf(x_1,\dots,x_n)=c. The sequence H1,,Hn\langle H_1,\dots,H_n\rangle is called increasing p-homogeneous for ff. We denote k IPTkn\forall k \ \mathsf{IPT}^n_k by IPTn\mathsf{IPT}^n. \end{definition}

We first prove that HT52\mathsf{HT}^{\leq 2}_5 implies IPT22\mathsf{IPT}^2_2 over RCA0\mathsf{RCA}_0 by a direct combinatorial argument.

\begin{proposition} RCA0HT52IPT22\mathsf{RCA}_0 \vdash \mathsf{HT}^{\leq 2}_5 \rightarrow \mathsf{IPT}^2_2 \end{proposition}

\begin{proof} We use the following notation: for nNn\in \mathbb{N}, if n=i03k0++it3ktn = i_0\cdot 3^{k_0} + \dots + i_t\cdot 3^{k_t} with k0<<ktk_0 \lt \dots \lt k_t and i0,,it{1,2}i_0,\dots,i_t \in \{1,2\}, we denote k0k_0 by λ(n)\lambda(n), ktk_t by μ(n)\mu(n), and i0i_0 by i(n)i(n). The following elementary properties hold (see 10, Theorem 3.1):

(P1) If λ(n)<λ(m)\lambda(n) \lt \lambda(m) then λ(n+m)=λ(n)\lambda(n+m)=\lambda(n) and i(n+m)=i(n)i(n+m)=i(n).

(P2) If λ(n)=λ(m)\lambda(n)=\lambda(m) and i(n)=i(m)=1i(n)=i(m)=1 then λ(n+m)=λ(n)\lambda(n+m)=\lambda(n) and i(n+m)=2i(n+m)=2.

(P3) If λ(n)=λ(m)\lambda(n)=\lambda(m) and i(n)=i(m)=2i(n)=i(m)=2 then λ(n+m)=λ(n)\lambda(n+m)=\lambda(n) and i(n+m)=1i(n+m)=1.

(P4) If μ(n)<λ(m)\mu(n) \lt \lambda(m) then λ(n+m)=λ(n)\lambda(n+m)=\lambda(n) and μ(n+m)=μ(m)\mu(n+m)=\mu(m).

\bigskip Let f:[N]22f:[\mathbb{N}]^2\rightarrow 2 be given. Define g:N5g:\mathbb{N}\rightarrow 5 as follows.

g(n):={0ifn=i3t,i{1,2},1+f(λ(n),μ(n))ifni3ti(n)=1,3+f(λ(n),μ(n))ifni3ti(n)=2.g(n):= \begin{cases} 0 & if n = i\cdot 3^t, i \in \{1,2\},\\ 1+f(\lambda(n),\mu(n)) & if n \neq i\cdot 3^t \wedge i(n)=1,\\ 3+f(\lambda(n),\mu(n)) & if n \neq i\cdot 3^t \wedge i(n)=2.\\ \end{cases}

Note that gg is well-defined since λ(n)<μ(n)\lambda(n)\lt \mu(n) if nn is not of the form i3ti\cdot 3^t, i{1,2}i\in\{1,2\}.

Let HH witnessing HT52\mathsf{HT}^{\leq 2}_5 for gg be an infinite set such that FS2(H)FS^{\leq 2}(H) is monochromatic under gg.

First, the color of FS2(H)FS^{\leq 2}(H) cannot be 00: the set HH cannot contain two terms 3p,3q3^p,3^q with p<qp \lt q since their sum is not of the form i3ri\cdot 3^r, and it cannot contain two terms 23p,23q2\cdot 3^p, 2\cdot 3^q with p<qp \lt q since their sum is not of the form i3ri\cdot 3^r.

Second, for all h,hFS2(H)h,h'\in FS^{\leq 2}(H), i(h)=i(h)i(h)=i(h'): strengthened to FS2(H)FS^{\leq 2}(H) instead of HH. Note that this is necessary for its application just below establishing (P6), and the same is true in the setting of 10, which needs a minor correction.} i(n)=1i(n)=1 implies g(n){1,2}g(n)\in\{1,2\} and i(n)=2i(n)=2 implies g(n){3,4}g(n)\in\{3,4\}. Then also the following property (P6) holds under the assumption that FS2(H)FS^{\leq 2}(H) (rather than FS3(H)FS^{\leq 3}(H), as in 10) is monochromatic for gg: for all k0k\geq 0 there is at most one nHn\in H such that λ(n)=k\lambda(n)=k. Suppose otherwise as witnessed by hhh\neq h' in HH with λ(h)=λ(h)\lambda(h)=\lambda(h'). Since we also have i(h)=i(h)i(h)=i(h'), it follows that i(h+h)i(h)=i(h)i(h+h')\neq i(h)=i(h'), contra (P5).

Hence we can sparsify HH (computably) so as to ensure the following

\begin{center} (Apartness Condition): if h<hh \lt h' are in HH then μ(h)<λ(h)\mu(h)\lt \lambda(h'). \end{center}

Assume without loss of generality that HH satisfies the apartness condition. Assume without loss of generality that the value i(h)i(h) for hHh\in H is 11. Let c{1,2}c\in \{1,2\} be such that FS2(H)FS^{\leq 2}(H) has color cc under gg.

Let

H1:={λ(n):nH}H_1 := \{\lambda(n)\,:\, n \in H\}
and
H2:={μ(n):nH}.H_2 := \{\mu(n)\,:\, n \in H\}.

We claim that H1,H2\langle H_1,H_2\rangle is increasing p-homogeneous for ff.

First observe that, letting H={h1,h2,}<H=\{h_1,h_2,\dots\}_\lt , we have H1={λ(h1),λ(h2),}<H_1 = \{ \lambda(h_1),\lambda(h_2),\dots\}_\lt and H2={μ(h1),μ(h2),}<H_2 = \{ \mu(h_1),\mu(h_2),\dots\}_\lt . This is so because λ(h1)<μ(h1)<λ(h2)<μ(h2)<\lambda(h_1)\lt \mu(h_1)\lt \lambda(h_2)\lt \mu(h_2)\lt \dots by the apartness condition and the fact that the color is not 00.

Then we claim that f(x1,x2)=c1f(x_1,x_2) = c-1 for every increasing pair (x1,x2)H1×H2(x_1,x_2)\in H_1\times H_2. Note that (x1,x2)=(λ(hi),μ(hj))(x_1,x_2) = (\lambda(h_i),\mu(h_j)) for some iji \leq j. If i=ji=j we have

c=g(hi)=1+f(λ(hi),μ(hi)),c = g(h_i) = 1+f(\lambda(h_i),\mu(h_i)),

and if i<ji<j we have

c=g(hi+hj)=1+f(λ(hi+hj),μ(hi+hj))=1+f(λ(hi),μ(hj)),c= g(h_i+h_j) = 1 + f(\lambda(h_i+h_j),\mu(h_i+h_j)) = 1 + f(\lambda(h_i),\mu(h_j)),

since FS2(H)FS^{\leq 2}(H) is monochromatic for gg with color cc. Thus, in any case

c=1+f(λ(hi),μ(hj))=1+f(x1,x2).c = 1+f(\lambda(h_i),\mu(h_j)) = 1 + f(x_1,x_2).

This shows that H1,H2\langle H_1,H_2\rangle is increasing p-homogeneous of color c1c-1 for ff. \end{proof}

Discussion

Proposition~ ? should be compared with Corollary 2.4 of 10: RCA0+BΣ20+IPT22SRT22\mathsf{RCA}_0 + B\Sigma^0_2 +\mathsf{IPT}^2_2 \vdash \mathsf{SRT}^2_2. Proposition~ ? has the following corollaries.

\begin{corollary} Over RCA0\RCA, HT52\mathsf{HT}^{\leq 2}_5 implies SRT22\mathsf{SRT}^2_2. \end{corollary}

\begin{proof} Dzhafarov and Hirst show that IPT22\mathsf{IPT}^2_2 implies D22\mathsf{D}^2_2 over RCA0\mathsf{RCA}_0 (Proposition 3.5 in ~9). Chong, Lempp and Yang have later proved that D22\mathsf{D}^2_2 implies SRT22\mathsf{SRT}^2_2 over RCA0\mathsf{RCA}_0 (Theorem 1.4 in 6). \end{proof}

Since SRT22\mathsf{SRT}^2_2 implies BΣ20B\Sigma^0_2, we also have the following corollary.

\begin{corollary} HT52\mathsf{HT}^{\leq 2}_5 is not provable in WKL0\mathsf{WKL}_0. \end{corollary}

Also, as Ludovic Patey kindly pointed out to us, IPT22\mathsf{IPT}^2_2 is known to be strictly stronger than SRT22\mathsf{SRT}^2_2: Theorem 2.2 in 7 showed that there is a non-standard model of SRT22+BΣ20\mathsf{SRT}^2_2+B\Sigma^0_2 having only low sets in the sense of the model. Lemma 2.5 in 9 can be formalized in RCA0\mathsf{RCA}_0 and shows that no model of IPT22\mathsf{IPT}^2_2 can contain only Δ20\Delta^0_2 sets. Thus, Proposition~ ? implies that HT52\mathsf{HT}^{\leq 2}_5 is strictly stronger than SRT22\mathsf{SRT}^2_2.

\bigskip The proof of Proposition~ ? is easily adapted to show \bc RCA0n(HT2n+12IPTn2)\mathsf{RCA}_0 \vdash \forall n (\mathsf{HT}^{\leq 2}_{2n+1}\rightarrow \mathsf{IPT}^2_n). \ec Then RCA0HT2IPT2\mathsf{RCA}_0 \vdash \mathsf{HT}^{\leq 2} \rightarrow \mathsf{IPT}^2. On the other hand we know that IPT2SRT2\mathsf{IPT}^2 \rightarrow \mathsf{SRT}^2, where SRT2\mathsf{SRT}^2 denotes the Stable Ramsey's Theorem for pairs and all colors (Dzhafarov and Hirst 9, Theorem 3.3). Finally, it is known that RCA0+SRT2BΣ30\mathsf{RCA}_0 + \mathsf{SRT}^2 \vdash \mathsf{B}\Sigma^0_3 (Cholak, Jockusch and Slaman 33, Section 11.2). Therefore we also have the following corollary.

\begin{corollary} Over RCA0\mathsf{RCA}_0, HT2\mathsf{HT}^{\leq 2} implies BΣ30\mathsf{B}\Sigma^0_3. \end{corollary}

The author has been up to now unable to lift the combinatorial argument in the proof of Proposition~ ? to show that HTk3\mathsf{HT}^{\leq 3}_k implies IPT23\mathsf{IPT}^3_2, for some k2k\geq 2. Note that by results of 9 and 10 the following holds: RCA0HT43IPT23\mathsf{RCA}_0 \vdash \mathsf{HT}^{\leq 3}_4 \rightarrow \mathrm{IPT}^3_2.

\part{Computational complexity theory}


11. Thompson: Symmetric functions can be computed by Boolean circuits of linear size and logarithmic depth

Declan Thompson and Matt Bray, Honour's students from Auckland University, visited the Research Centre Coromandel in February. Declan worked on Boolean circuits, connecting to the CompSci 750 class on computational complexity which Andr\'e had co-taught in Semester 2, 2015. \vsp

A function f ⁣:{0,1}n{0,1}f\colon \, \{0,1\}^n\to \{0,1\} is symmetric if its value does not depend on the order of its arguments. For Boolean symmetric functions, this means that the output depends only on the number of 11s in the input. It is not hard to see that given a binary representation of the number of 11s in the input, a Boolean circuit of linear size and logarithmic depth can compute the value of a symmetric function. So it suffices to find an efficient method for obtaining this binary representation from the original input. Circuits exist which add binary numbers in linear size and logarithmic depth (see, for example, the Krapchenko adder of 43). A n\"aive approach to counting the number of 11s is to treat each input as an individual number and utilise an adding tree. Unfortunately this requires a circuit of more than logarithmic depth. Instead, we will utilise so called ``3-for-2'' adders and finally only one Krapchenko adder. A full adder is a circuit for calculating the sum of three bits. Figure Fig. 1 gives a construction for a full adder. There are three input bits and two output bits, representing the two bit output. A carry save adder (CSA) utilises a chain of full adders to take three nn-bit inputs a,b,ca,b,c and return two n+1n+1-bit outputs u,vu,v such that a+b+c=u+va+b+c = u+v. The CSA works by sending sum bits (y1y_1 in Figure Fig. 1) to uu and carry bits (y2y_2) to vv. Specifically, if the full adder returns y2y1y_2y_1 from ai,bi,cia_i, b_i, c_i, then ui=y1u_i = y_1 and vi+1=y2v_{i+1} = y_2. We set un=v0=0u_n = v_0 = 0. As an example, consider the following sum.

100110100110
111101111101
+99101101\underline{+\phantom{99}101101}
0110110=u0110110 \quad = u
1011010=v1011010 \quad = v

A full adder. <span class=x1+x2+x3=y2y1x_1 + x_2 + x_3 = y_2y_1. \oplus denotes addition modulo 22." loading="lazy" style="max-width:100%">
Figure 1. A full adder. x1+x2+x3=y2y1x_1 + x_2 + x_3 = y_2y_1. \oplus denotes addition modulo 22.

A full adder has a constant number of gates and a CSA uses a full adder for each bit. Hence a CSA uses O(n)O(n) size circuits with depth constant, where nn is the number of bits of each input number. We construct an adder tree for x0,xn1x_0, \dots x_{n-1} by running CSAs in parallel and then combining their outputs. At the first ``level'', there are 13n\frac{1}{3}n CSAs each taking in three 11 bit inputs and returning two 22 bit outputs (4 wires in total). At the second level there are 13n2\frac{1}{3}n\cdot2 total inputs and each CSA takes three inputs, so there are 1323n\frac{1}{3}\frac{2}{3}n CSAs. In general, at the jthjth level there are 1323j1n\frac{1}{3}\frac{2}{3}^{j-1}n CSAs taking three jj bit inputs and returning two j+1j+1 bit outputs. Each CSA decreases the number of numbers to add by 11 until we are left with two binary numbers. Hence we require n2n-2 CSAs. Logarithmic depth of the adder tree is easy to establish. Each CSA has constant depth and since we combine them in a tree fashion the depth of CSAs is logarithmic. Each CSA has size proportional to the number of bits in the inputs. From this, we can conclude that the size of the adder tree is approximately \[ O(\frac{1}{3}n\sum_{j=1}^{\lfloor\log n\rfloor}\frac{2}{3}^{j-1}j). \] However j=123j1j=9\sum_{j=1}^{\infty}\frac{2}{3}^{j-1}j = 9 and so in fact the adder tree is of size O(n)O(n). Thus we have obtained two binary numbers which add to the total number of 11s in the input, using linear size and logarithmic depth circuits. It is now a simple process to use a linear size, logarithmic depth adder (such as Krapchenko's) to obtain a single binary number, which can then be used to determine the output of an arbitrary symmetric function.


12. Describing ordinals less than $ \varepsilon_0$ by finite trees

Andreas Weiermann, Paul Shafer and Nies discussed in Ghent in March. This discussion connected some well-known facts.

For this note a tree BB is an acyclic connected directed finite graph with a distinguished root rr. BB can be naturally viewed as a finite subset of ω<ω\omega^{\lt \omega} (sequences of natural numbers) closed under initial segments; rr is the empty string. If BrB \neq r then BB is given by a tuple (B1,,Bn)(B_1, \ldots, B_n) of trees, where the BiB_i correspond to the successors of rr from left to right.

The ordinal o(B)o(B) is defined recursively as follows: let o(r)=0o(r) = 0. If B=(B1,,Bn)B= (B_1, \ldots, B_n) then \bc o(B)=i=1nωo(Bπ(i))o(B) = \sum_{i=1}^n \omega^{o(B_{\pi(i)})} \ec where π\pi is a permutation of {1,,n}\{1, \ldots, n\} such that o(Bπ(1))o(Bπ(n))o(B_{\pi(1)}) \ge \ldots \ge o(B_{\pi(n)}).

The norm N(α)N(\alpha) of an ordinal α<ϵ0\alpha \lt \epsilon_0 is defined by N(0)=0N(0) = 0 and N(γ)=1+N(α)+N(β)N(\gamma) = 1 + N(\alpha) + N(\beta) if γ\gamma has Cantor normal form ωα+β\omega^\alpha +\beta. Clearly each γ<ε0\gamma \lt \varepsilon_0 has the form o(B)o(B) for some tree BB, and N(γ)N(\gamma) is the number of edges of such a tree. The ordinal of a tree is a complete invariant for tree isomorphism: \begin{prop} Let B,CB, C be trees. We have \bc BCo(B)=o(C)B \cong C \LR o(B)= o(C). \ec \end{prop} \begin{proof}First suppose that ρ ⁣:BC\rho \colon B \cong C. If B=C=rB=C = r then o(B)=o(C)=0o(B) =o(C) =0. Otherwise B=(B1,,Bn)B = (B_1, \ldots, B_n), C=(C1,,Cn)C = (C_1, \ldots, C_n) and ρ ⁣:BiCσ(i)\rho \colon B_i \cong C_{\sss(i)} for σSn\sss \in S_n. Inductively we have o(Bi)o(Cσ(i))o(B_i) \cong o(C_{\sss(i)}). Choose πSn\pi \in S_n such that o(Bπ(1))o(Bπ(n))o(B_{\pi(1)}) \ge \ldots \ge o(B_{\pi(n)}). Then o(Cσ(π(1)))o(Cσ(π(n)))o(C_{\sss(\pi(1))}) \ge \ldots \ge o(C_{\sss(\pi(n))}). Therefore o(B)=o(C)o(B)= o(C). Now suppose α=o(B)=o(C)\alpha = o(B)= o(C). If α=0\alpha=0 we have BCB \cong C trivially. Otherwise write α\alpha in Cantor normal form i=1nωβi\sum_{i=1}^n \omega^{\beta_i} where β1βn\beta_1 \ge \ldots \ge \beta_n. Since CNF is unique we have B=(B1,,Bn)B = (B_1, \ldots, B_n), C=(C1,,Cn)C = (C_1, \ldots, C_n) with βi=o(Bπ(i))=o(Cθ(i))\beta_i= o(B_{\pi(i)}) = o(C_{\theta(i)}) for π,θSn\pi, \theta \in S_n. This shows that BCB \cong C. \end{proof}

The number of ordinals α\alpha with N(α)=nN(\alpha)= n is asymptotically (2.95)nn1.5(2.95)^n n^{-1.5} by a result of Weiermann. The number of trees with nn edges is (2nn)/(n+1)\binom {2n} n /(n+1) (Catalan number), which is asymptotically 4nn1.5/π4^n n^{-1.5}/\sqrt \pi (much larger).

A tree BB is canonical if BB is a root, or B=(B1,,Bn)B = (B_1, \ldots, B_n) for canonical trees BiB_i such that o(B1)o(Bn)o(B_1) \ge \ldots \ge o(B_n). Clearly each ordinal less than ϵ0\epsilon_0 is o(B)o(B) for a unique canonical tree. Isomorphism and canonization is in LOGSPACE by a result of Aho, Hopcroft and Ullman. Also see Buss 1995 where algorithms in the smaller class ALOGSPACE are given.

\begin{question} How can one generate a random ordinal with given norm nn using poly(nn) steps and the appropriate number of nlog2(2.95)n \log_2 (2.95) of random bits? \end{question} This amounts to generating a random canonical tree with nn edges.


13. Nies and Scholz: Grothendieck's constants

(Written by Nies after some discussion with Volkher Scholz, who works at U Gent in the research group of Prof. Verstraete, and visited Auckland in April.) Let F\mathbb F be one of the fields R,C\RR, \mathbb C. Choose scalars from F\mathbb F. A.\ Grothendieck proved in 1953 that there are positive constants KGFK_G^\mathbb F as follows.

Let C=\seq{\gamma_{i,k}} be an n×nn \times n matrix such that

i,kγi,kaibksupiaisupkbk \sum_{i,k} \gamma_{i,k} a_i b_k \le \sup_i |a_i| \sup_k |b_k|
for each scalars ai,bka_i, b_k. Then for each Hilbert space HH over F\mathbb F, and vectors xi,ykHx_i, y_k \in H (1i,kn1\le i,k \le n) \[ \sum_{i,k} \gamma_{i,k} \la x_i, y_k \ra \le K_G^\mathbb F \sup_i ||x_i|| \sup_k ||x_k||. \] See the reprinted paper~19. In (Eq. 1) we may assume that ai=bk=1|a_i| = |b_k| =1 because for fixed CC the inequality describes a convex set, so it suffices to look at its extreme points. Given the matrix CC as an input, it is known, that the condition in NP-hard. Say for R\RR the problem Max-Cut can be reduced to it (which asks given a graph whether one can partition the set of vertices into two sets so that the number of crossing edges is above a threshold). Easy matrices CC satisfying the condition are: n1In^{-1} I, or the one where each γi,k\gamma_{i,k} equals n2n^{-2}. We can get away with finite-dimensional Hilbert spaces. However the dimension of HH must be unbounded. E.g the value of KGRK^\RR_G for dimension 22 is 2\sqrt 2.

Interestingly, G's work is closely related to, but predated the Bell inequality (1964). The transition from a problem in real analysis to the setting of Hilbert space corresponds to the transition from classical to quantum physics. The real Grothendieck constant can be viewed as an upper bound on the possible violation of Bell's inequality in a quantum system. The precise values of the constants are not known. We know that (see 34) \[ 1 < K_G^{\mathbb C} < K_G^\RR < 1.782.\] Raghavendra and Steurer \cite[Thm 1.3]{Raghavendra.Steurer:09} prove that KGRK^\RR_G is a computable real, and in fact computable up to precision η>0\eta>0 in time proportional to exp(exp(O(η3))\exp(\exp(O(\eta^{-3})). No surprise we still don't know what its value is.

\part{Group theory and its connections to logic}


14. Doucha and Nies: Primitive group actions in the setting of Polish Spaces

Michal Doucha and Nies worked at the RCC in 2014/2015. \begin{definition} Let GG be a Polish group and XX a Polish GG-space with all orbits dense. (G,X)(G,X) is called imprimitive if there exists a closed proper subset DXD\subseteq X such that for every gGg\in G either gD=Dg\cdot D=D or gDD=g\cdot D\cap D=\emptyset and moreover, DD intersects some orbit in at least two elements. I.e., xyDgG[gx=y]\ex x \neq y \in D \ex g \in G [ g \cdot x =y]. The set DD is called a closed domain of imprimitivity. Otherwise, (G,X)(G,X) is called primitive. \end{definition} Given an action GXG \curvearrowright X, we say that an equivalence relation EE on XX is GG-invariant if for every gGg\in G and every x,yXx,y\in X we have xEygxEgyx E y\lra g\cdot x E g\cdot y. Equivalently, g[x]E=[gx]Eg \cdot [x]_E= [g\cdot x]_E for each gGg\in G and xXx \in X. \begin{prop} Given a Polish group GG and a Polish GG-space XX with all orbits dense, TFAE:

\bi \item[(i)] (G,X)(G,X) is imprimitive \item[(ii)] there exists a GG-invariant smooth equivalence relation EE on XX other than idX\mathrm{id}_X or X2X^2, with all equivalence classes closed, such that some equivalence class intersects some orbit in at least two elements. \item[(iii)] as in (ii) but without the restriction to smoothness. \ei \end{prop} \begin{proof} (iii)\to(i) Let D=[x]ED=[x]_E be an equivalence class of EE that intersects some orbit in at least two points. We claim that DD is a closed domain of imprimitivity. It is clearly closed and properly contained in XX. For each gGg\in G, if gxExgx E x we have gD=[gx]E=DgD = [gx]_E= D. Otherwise gDD=gD \cap D = \ES.

\n (i)\to(ii). Let DD be a closed domain of imprimitivity. Let \bc H={hG:hD=D}H=\{h\in G: h\cdot D=D\}. \ec Clearly, HH is a closed subgroup of GG. Since every orbit in XX is dense and DD is a proper subset, HH is a proper subgroup of GG.

Let us define a relation EE on XX. For x,yXx,y\in X we define \bc xEygG[g1xDg1yDx E y \lra \exists g\in G [ g^{-1}\cdot x \in D \lland g^{-1}\cdot y \in D. \ec We shall prove that EE is a smooth GG-invariant equivalence relation with closed classes such that some class intersects some orbit in at least two elements.

Since for every gGg\in G the map xgxx\to g\cdot x is a homeomorphism of XX we have that for each gGg\in G the set gDg\cdot D is also closed. Denote by X/DX/D the set {gD:gG}\{g\cdot D:g\in G\}. We claim for every F1F2X/DF_1\neq F_2\in X/D we have F1F2=F_1\cap F_2=\emptyset. Indeed, write FiF_i as giDg_i\cdot D for giGg_i\in G, where i{1,2}i\in \{1,2\}. If g1Dg2Dg_1\cdot D\cap g_2\cdot D\neq \emptyset, then D(g11g2)DD\cap (g_1^{-1}\cdot g_2)\cdot D\neq \emptyset. Thus by assumption (g11g2)D=D(g_1^{-1}\cdot g_2)\cdot D=D, so g1D=g2Dg_1\cdot D=g_2\cdot D, a contradiction. It follows that X/DX/D is the set of EE-classes. In particular, EE is an equivalence relation with each equivalence class being closed and the EE-class DD intersects by assumption some orbit in at least two elements.

Consider the quotient G/HG/H consisting of left cosets of HH with the quotient topology. It is a folklore fact that this is a Polish space metrizable by the metric δ\delta defined for any g1H,g2Hg_1\cdot H, g_2\cdot H as the Hausdorff distance \bc δ(g1H,g2H)=inf{dG(h1,h2):h1g1H,h2g2H}\delta(g_1\cdot H,g_2\cdot H)=\inf\{d_G(h_1,h_2): h_1\in g_1\cdot H,h_2\in g_2\cdot H\}, \ec where dGd_G is some compatible right-invariant metric on GG. See for example 16 for details. Let us define the map ϕ:XG/H\phi:X\rightarrow G/H as follows: \bc ϕ(x)=gH\phi(x)=g\cdot H if g1xDg^{-1}\cdot x\in D. \ec This is well-defined since HH fixes DD. We now claim that ϕ\phi is a Borel reduction of EE into id(G/H)\mathrm{id}(G/H). This will show that EE is smooth.

To show that it is a reduction, pick some x,yXx,y\in X. Suppose that xEyx E y. Then by definition there is gGg\in G such that g1xg^{-1}\cdot x and g1yg^{-1}\cdot y lie in DD, thus ϕ(x)=ϕ(y)=gH\phi(x)=\phi(y)=g\cdot H. On the other hand, if ϕ(x)=ϕ(y)=gH\phi(x)=\phi(y)=g\cdot H, then g1xg^{-1}\cdot x and g1yg^{-1}\cdot y lie in DD.

It remains to check that ϕ\phi is Borel. We show that ϕ\phi factorizes through X/DX/D as ψπ\psi\circ \pi, where π:XX/D\pi:X\rightarrow X/D is the canonical projection and ψ:X/DG/H\psi:X/D\rightarrow G/H sends gDg\cdot D to gHg\cdot H. We note that a set UX/DU\subseteq X/D is open if and only if U\bigcup U is open in XX. Then we show that ψ\psi is continuous (even open) and ψ\psi is a bijection whose inverse ψ1\psi^{-1} is continuous, that suffices.

That π\pi is continuous (and open) follows directly from the definition of the topology on X/DX/D. Also, it is clear that ψ\psi is a bijection. We check that ψ1\psi^{-1} is continuous. Let UX/DU\subseteq X/D be an open neighbourhood of some gDg\cdot D. Pick arbitrarily some xDx\in D. Since U\bigcup U is an open neighbourhood of xx and the group action is continuous there exists an open neighbourhood VV of gg such that for every hVh\in V we have hxUh\cdot x\in \bigcup U. We have that VH=VHV_H=V\cdot H is an open neighbourhood of gHg\cdot H in G/HG/H and we claim that ψ1(VH)U\psi^{-1}(V_H)\subseteq U. This is immediate. Any element of VHV_H is of the form hHh\cdot H for some hVh\in V and thus sent by ψ1\psi^{-1} to hDh\cdot D. We have that hxUh\cdot x\in \bigcup U and since U\bigcup U is EE-invariant we have that hDUh\cdot D\subseteq \bigcup U, thus hDUh\cdot D\in U. \end{proof} \begin{prop} Let GG be a Polish group and XX a Polish GG-space with all orbits dense. Suppose that for any xXx\in X the stabilizer GxG_x is a maximal closed subgroup of GG. Then (G,X)(G,X) is primitive. \end{prop} \begin{proof} Suppose that (G,X)(G,X) is imprimitive, so there exists a closed domain of imprimitivity DXD\subseteq X. Let H={hG:hD=D}H=\{h\in G:h\cdot D=D\}. HH is clearly a closed subset of GG. Moreover, since DD is a closed domain of imprimitivity we have that HH is a group. Let xXx\in X be such that we have DGx2|D\cap G\cdot x|\geq 2. We may suppose that xDx\in D. We have that GxHG_x\leq H. We shall show that Gx<H<GG_x<H<G and that will be a contradiction with the maximality of GxG_x. By assumption there exists hGGxh\in G\setminus G_x such that hxDh\cdot x\in D. Since DD is a domain of imprimitivity, so for every gGg\in G we have either gD=Dg\cdot D=D or gDD=g\cdot D\cap D=\emptyset, we must have that hD=Dh\cdot D=D and thus hHh\in H. We have shown that Gx<HG_x<H. On the other hand, DD is a proper closed subset of XX and since the orbit of xx is dense, there exists gGg\in G such that gxDg\cdot x\notin D and thus gDD=g\cdot D\cap D=\emptyset and gHg\notin H. We have shown that H<GH<G and the proof is complete. \end{proof}

\n Questions.

\n 1. How about the converse implication in Prop. ~ ??

\n 2. Robinson \cite[7.2.5]{Robinson:82} states that if GG is primitive on XX, then every nontrivial normal subgroup is transitive. (The latter property is called quasiprimitive by Cheryl Praeger.) Check this in the Polish setting, where the normal subgroup is closed, and we have topological transitivity in that every orbit is dense.


15. Nies and Tent: a sentence of size $O(\log n)$ expressing that a group has $n$ elements

This post is related to Nies' and Tent's article ``Describing finite groups by short first-order sentences" 32. We use the definition logn=min{r ⁣:2rn}\log n = \min \{ r \colon \, 2^r \ge n\}. In that article we gave a description of any finite group GG via a first order sentence of length O(log3G)O (\log^3|G|). Here we want to express that the group has size nn by a first-order sentence of length O(logn)O(\log n). This will also yield a new way to describe the finite simple groups in length O(logn)O(\log n), still relying on CFSG but not relying on the short presentations in 20 This work happened in March 2016 at UCLA, after some preliminary work of Nies with the honour's student Matthew Bray. At the BIRS permutation groups meeting Nov 13-18, Csaba Schneider and David Craven provided the crucial references needed to distinguish by short first order sentences the few examples of non isomorphic simple groups of the same size.

\begin{thm} For each nn there is a sentence ϕn\phi_n in the first order language of groups such that ϕn=O(logn)|\phi_n | = O (\log n) and for each group GG, \bc GϕnG=nG \models \phi_n \LR |G| = n. \ec \end{thm}

We first provide some necessary facts. We use \cite[Lemma 2.1]{Nies.Tent:17}:

\begin{lemma} For each positive integer rr, there is an existential formula θr(g,x)\theta_r(g,x) in the first-order language of monoids L(e,)L(e, \circ), of length O(logr)O(\log r), such that for each monoid MM, Mθr(g,x)M \models \theta_r(g,x) if and only if xr=gx^r=g.

\end{lemma} In particular, we can express that a group GG has exponent dividing rr using O(logr)O(\log r). The following variant is also needed.

\begin{lemma} For each positive integer kk, there is a formula ψr(y,x)\psi_r(y,x) in the first-order language of monoids L(e,)L(e, \circ), of length O(logr)O(\log r), such that for each monoid MM, Mψr(g,x)M \models \psi_r(g,x) if and only if xi=gx^i=g for some ii with 0ir0 \le i \le r. \end{lemma} \begin{proof} Let ψ1(y,x)y=1y=x\psi_1(y,x) \equiv y=1 \lor y=x. Recursively define

\begin{eqnarray*} \psi_{2k}(y,x) & \equiv & \ex u,v [ y = uv \land \fa z. (z=u \lor z=v) \psi_k(z,x)] \\ \psi_{2k+1}(y,x) &\equiv & \ex u,v [ (y = uv \lor y = uvx) \land \fa z. (z=u \lor z=v) \psi_k(z,x)] \end{eqnarray*} Clearly ψr\psi_r works as required. Further, ψr=O(logr)|\psi_r| = O(\log r). \end{proof}

We next provide an easy fact on pp-groups (which is not first order at this stage).

\begin{fact} Suppose LL is a pp-group. Then Lpr|L|\le p^r \LR

x1,,xrLyL\ex x_1, \ldots, \ex x_r \in L \fa y \in L
a1,,ar[0ai<py=ixiai]. \ex a_1, \ldots, a_r \, [ 0\le a_i \lt p \land \, y = \prod_i x_i^{a_i}].

\end{fact} \begin{proof} The implication \LA is immediate.

For the implication \RA, we use induction on rr. The base case r=1r=1 is obvious since LL is trivial or cyclic of order pp. Now suppose r>1r \gt 1 and the implication holds for r1r-1. If LL is non-trivial, pick xrx_r in the centre of order pp. By inductive hypothesis for L/NL/N where N=xrN = \la x_r \ra, we can choose x1,,xr1Lx_1, \ldots, x_{r-1} \in L such that statement holds in L/NL/N via xiNx_i N, 1i<r1 \le i \lt r. So for each yLy \in L, we have

yN=i=1r1(xiN)ai=i=1r1(xi)aiNyN = \prod_{i=1}^{r-1} (x_iN)^{a_i}= \prod_{i=1}^{r-1} (x_i)^{a_i}N

for some aia_i with 0ai<p0 \le a_i \lt p. Therefore there is ara_r with 0ar<p0 \le a_r \lt p such that y=ixiaiy = \prod_i x_i^{a_i}, as required. \end{proof}

\begin{lemma} For k=prk=p^r, pp prime, rNr \in \NN there is a sentence βk\beta_{k} of length O(logk)O(\log k) such that GβkG \models \beta_{k} iff GG has a subgroup of size kk. \end{lemma} \begin{proof} We express ()(\diamond) by a first-order sentence of length O(logk)O(\log k) via the formulas in Lemma~ ?:

\begin{eqnarray} \chi_k(y; x_1, \ldots, x_r) & \equiv & \ex s_0, \ldots, s_r \\ && [ s_0 = 1 \land s_r=y \land \bigwedge_{i=1}^r \ex v \, ( \psi_{p-1} (v, x_i) \land s_i = s_{i-1}v)].\end{eqnarray} The length of χk|\chi_k| is O(rlogp)=O(logk)O(r \log p) = O(\log k).

Given a group GG and x=x1,,xrG\ol x = x_1, \ldots, x_r \in G, write Uxk={yG ⁣:Gχk(y;x)}U^k_{\ol x} = \{y \in G \colon \, G\models \chi_k(y; \ol x)\}. The sentence βk\beta_k expresses that there is x=x1,,xr\ol x = x_1, \ldots, x_r such that UxkU^k_{\ol x} is a subgroup of exponent dividing kk, and rr is optimal, namely, there is no y=y1,yr1\ol y = y_1, \ldots y_{r-1} such that Uyk/p=UxkU^{k/p}_{\ol y} = U^k_{\ol x}.

If GG has a subgroup LL of size kk then GβkG \models \beta_k by Fact~ ?. Now suppose GβkG \models \beta_k via x1,xrGx_1, \ldots x_r \in G. Then L=UxkL= U^k_{\ol x } is a subgroup of GG of size kk. \end{proof}

\begin{proof}[Proof of Thm.\ ?] Using Lemma~ ? we can express that the group GG has exponent dividing nn. In particular, only prime factors of nn can occur in the order of GG. Suppose n=i=1mpirin = \prod_{i=1}^m p_i^{r_i} for prime numbers p1,,pmp_1, \ldots, p_m. We express using Lemma~Eq. 2 for each imi \le m that there is a Sylow subgroup of size pirip_i^{r_i}. For each ii this takes length O(log(piri))O(\log(p_i^{r_i})) with the OO-constant independent of ii. So the resulting sentence has length O(logn)O(\log n). \end{proof}

It would be interesting to find sentences as in Theorem~ ? with a bounded number of quantifier alternations.

Next we express in logarithmic length that a group is simple. We use \cite[Lemma 2.3]{Nies.Tent:17} on generation. The notation is adapted slightly. \begin{lemma} For each positive integers k,vk,v, there exists a first-order formula αkv(g;z1,,zk)\alpha^v_k(g;z_1,\ldots,z_k) of length O(k+logv)O(k+\log v) such that for each group GG of size at most vv, Gαkv(g;z1,,zk){G \models \alpha^v_k(g;z_1,\ldots,z_k)} if and only if gz1,,zk{g \in \langle z_1,\ldots,z_k \rangle}. \end{lemma}

Given a group GG of size at most vv, we write Lkv(z)={yG ⁣:Gαkv(y;x)}L^v_k({\ol z}) = \{y \in G \colon \, G\models \alpha^v_k(y; \ol x)\} in case this is a subgroup.

Every finite group has a generating set of logarithmic size. So a group GG of size at most vv is simple iff \bc Gz1,,zk[Lkv(z)G(Lkv(z)={e}Lkv(z)=G)]G \models \fa z_1,\ldots,z_k \, [ L^v_k({\ol z}) \lhd G \to ( L^v_k({\ol z}) = \{e\} \lor L^v_k({\ol z}) = G)], \ec where k=logvk = \log v.

One can use these facts to give a new type of first-order description of finite simple groups in logarithmic length. First one says what the size of the groups is, and that it is simple. A finite simple group is determined by its size, with the exception of \bi \item PSL3(4)\mathtt{PSL}_3(4) which has the same size as Alt8\mathtt{Alt}_8 without being isomorphic to it, and \item the groups Bn=PΩ2m+1(q)B_n= P\Omega_{2m+1}(q) and Cm=PSp2m(q)C_m=PSp_{2m}(q), qq an odd prime power, m>2m \gt 2, which have the same size 12qm2i=1m(q2i1)\frac 1 2 q^{m^2} \prod_{i=1}^m (q^{2i}-1) without being isomorphic. \ei (See http://mathoverflow.net/questions/107620/non-isomorphic-finite-simple-groups for background.) The exceptional cases above can be distinguished by the fact that the nonisomorphic groups of the same size have different numbers of conjugacy classes of involutions, and that the number of these conjugacy classes is logarithmic in the size. Firstly, in PSL3(4)\mathtt{PSL}_3(4) all involutions are conjugate, while in A8A_8 there are two conjugacy classes, namely (12)(34)(12)(34) and (12)(34)(56)(78)(12)(34)(56)(78). Next, in BmB_m there are mm classes, in CmC_m for mm odd there are (m+1)/2(m+1)/2 classes and for mm even there are m/2+1m/2+1 classes. For the latter, see \cite[Table 4.5.1, p.\ 172]{Gorenstein.ea:98}. To read this table, note that classes in the simple group are the coset `1', diagonal involutions (outer automorphisms of the simple group) are labelled `d'. The notation 1/d1/d [condition] means 1 if condition holds, dd if condition does not hold. (Thanks to David Craven for pointing out the reference and explaining this.)

We note that \cite[Lemma 2.5]{Kimmerle.etal:90} shows that the number of involutions of BmB_m, CmC_m also differs for m>2m>2. This could also be used. (Thanks to Csaba Schneider for this reference.)


16. Melnikov and Nies: A computable compact abelian group such that the Haar measure is not computable

Melnikov and Nies worked at the Research Centre Coromandel in June. Recall a computable topological space XX is given by a sequence of basis sets \seq {B_n} \sN n such that for every two such sets Bi,BkB_i,B_k we can uniformly represent BiBkB_i \cap B_k as an effective union of basic sets. Each computable metric space is also a computable topological space with the basis given by the Bδ(p)B_\delta(p) for δQ+\delta \in \QQ^+ and pp a special point. We say that a Borel measure μ\mu on XX is computable if μ(Bi)\mu(B_i) is uniformly left-c.e. in ii (if boundaries of open sets are null we could as well require that is it uniformly computable).

A computable topological group is a group GG that is also a computable topological space, in such a way that the group operations are effectively continuous.

Recall that every separable compact group has a unique translation invariant probability measure, called the Haar measure. \begin{thm} There is a computable compact abelian group such that the Haar measure is not computable. \end{thm} \begin{proof} Let KK denote the halting problem with effective enumeration \seq{K_s}; we may assume that K2=K_2 = \ES. We first give uniformly in ee a presentation of a discrete cyclic group GeG_e such that the Haar measure on GeG_e is not uniformly computable.

For a real θ\theta let [θ]=e2πiθ[\theta]= e^{2 \pi i \theta}. The distance between to points on the circle is the usual shortest arc length.

We define a computable real v=vev= v_e uniformly in ee; [ve][v_e] will be a generator of GeG_e seen as a subgroup of the circle group. At stage ss, if e∉Kse \not \in K_s, define vs=12+2sv_s = \frac 1 2 + \tp {-s}. If eKsKs1e\in K_s \setminus K_{s-1} define vt=vs1v_t = v_{s-1} for all tst \ge s.

The special points of GeG_e are the uniformly computable reals given by the Cauchy name \seq{i v_{s+i}}_{\sN s}. If e∉Ke \not \in K then Ge={[0],[1/2]}G_e = \{ [0], [1/2]\}; if eKe \in K then Ge8|G_e | \ge 8.

The discrete topology on GeG_e is uniformly computable: as an effective basis take the sets GeBδ([ive])G_e \cap B_\delta([i v^e]) for δQ(0,1/2]\delta \in \QQ \cap (0,1/2]. Let μe\mu_e be Haar measure on GeG_e with the discrete topology. Clearly by the translation invariance of μe\mu_e we have e∉Kμe(B1/8(1))>1/4e \not \in K \lra \mu_e(B_{1/8}(1)) \gt 1/4. So μe\mu_e is not uniformly computable.

Now let G=eGeG= \prod_e G_e topologized with the product topology which is compact and effective with the usual product basis. Let pe ⁣:GGep_e \colon G \to G_e be the projection onto GeG_e which is computable uniformly in ee. If the Haar measure on GG is computable then the image measure pe(μ)p_e(\mu) on GeG_e is uniformly computable. However, μe=pe(μ)\mu_e= p_e(\mu) by uniqueness of Haar measure, contradiction. \end{proof}


17. Fouche and Nies: computable profinite groups

Willem Fouch\'e and Nies went on a 1-week retreat near Port Elizabeth, South Africa, and before and after worked at Unisa Pretoria. As one topic they studied randomness in computable profinite groups.

Background on profinite groups

A separable compact group GG is called profinite if GG is the inverse limit
G =\varprojlim_n \seq {G_n, p_n}\sN n
of a system of discrete finite groups
pnGnpn1Gn1p2G1.\to_{p_n} G_n \to_{p_{n-1}} G_{n-1} \to \ldots_{p_2} \to G_1.
The inverse limit is determined up to isomorphism by the universal property formulated in terms of category theory. For a concrete instantiation, it can be seen as a closed subgroup UU of the direct product nGn\prod_{n} G_n consisting of the functions α\alpha such that pn(α(n+1))=α(n)p_{n}(\alpha (n+1)) = \alpha(n) for each n>0n>0.

We may assume that the maps pnp_n are onto after replacing GnG_n by its subgroup of elements such that all the iterated pre-images under the maps pip_i are defined. This corresponds to pruning a tree by removing dead ends.

\begin{remark}[Haar measure] Given GG as an inverse limit of an onto system, the Haar probability measure μ\mu can be concretely defined as follows. Let qn ⁣:GGnq_n \colon G \to G_n be the natural projection. A clopen set CC of GG has the form C=qn1(F)C = q_n^{-1} (F) for a finite set FGnF \sub G_n. By definition μ\mu is translation invariant, so μ(C)=F/Gn\mu (C) =|F|/|G_n|. As the clopen sets form a basis this determines the measure on all the Borel sets of GG. \end{remark}

Completion

The definition below is taken from \cite[Section 3.2]{Ribes.Zalesski:00}. Let GG be a group, \+V\+ V a set of normal subgroups of finite index in GG such that U,V\+VU, V \in \+ V implies that there is W\+VW \in \+ V with WUVW \sub U \cap V. We can turn GG into a topological group by declaring \+V\+ V a basis of neighbourhoods (nbhds) of the identity. In other words, MGM \sub G is open if for each xMx \in M there is U\+VU \in \+ V such that xUMxU \sub M. \begin{definition} The completion of GG with respect to \+V\+ V is the inverse limit
G\+V=limU\+VG/U,G_{\+ V} = \varprojlim_{U \in \+ V} G/U,
where \+V\+ V is ordered under inclusion and the inverse system is equipped with the natural maps: for UVU \sub V, the map pU,V ⁣:G/UG/Vp_{U,V} \colon G/U \to G/V is given by gUgVgU \mapsto gV. \end{definition} The inverse limit can be seen as a closed subgroup of the direct product U\+VG/U\prod_{U \in \+ V} G/U (where each group G/UG/U carries the discrete topology), consisting of the functions α\alpha such that pU,V(α(gU))=gVp_{U,V}(\alpha (gU)) = gV for each gg. Note that the map g(gU)U\+Vg\mapsto (gU)_{U \in \+ V} is a continuous homomorphism GG\+VG \to G_{\+ V} with dense image; it is injective iff \+V={1}\bigcap \+ V = \{1\}. If the set \+V\+ V is understood from the context, we will usually write G^\widehat G instead of G\+VG_\+ V.

Free profinite groups

\begin{definition} Let F^k\widehat F_k be the free profinite group in kk generators x0,,xk1x_0, \ldots, x_{k-1} (k<ωk \lt \omega). \end{definition} Clearly, F^k\widehat F_k is the profinite completion of the abstract free group on kk generators with respect to the system of all subgroups of finite index. Any topologically finitely generated profinite group can be written in the form \[ \widehat F_k / R\] for some kk and a closed normal subgroup RR of F^k\widehat F_k.

\begin{definition} Let F^ω\widehat F_\omega be the free profinite group on a sequence of generators x0,x1,x2x_0, x_1, x_2 \ldots converging to 11 \cite[Thm.\ 3.3.16]{Ribes.Zalesski:00}. \end{definition} Thus, F^ω\widehat F_\omega is the completion in the sense of the previous subsection of the free group FωF_\omega on generators x0,x1,x_0, x_1, \ldots with respect to the system of normal subgroups of finite index that contain almost all the xix_i. Any profinite group GG has a generating sequence \seq{g_i}\sN i converging to 11. This is easy to see using coset representatives for a descending sequence of open normal subgroups that form a fundamental system of nbhds of 1G1_G. (Also see \cite[Prop. 2.4.4 and 2.6.1]{Ribes.Zalesski:00}.) By the universal property of the completion, the map from the abstract free group induced by xigix_i \to g_i extends to a continuous epimorphism F^ωG\widehat F_\omega \to G. So GG can be written in the form \[ \widehat F_k / R\] where RR is a closed normal subgroup of F^k\widehat F_k.

``Almost everywhere" theorems in profinite groups

\begin{thm}[Jarden; see 15, 18.5.6] Let G=Gal(Qˉ/Q)G = \mathrm{Gal}(\bar \QQ / \QQ) be the absolute Galois group of Q\QQ. For almost all tuples σ=(σ1,,σe)Ge\sss= (\sss_1, \ldots, \sss_e) \in G^e, the closed subgroup of GG topologically generated by σ\sss, is a free profinite group of rank ee. \end{thm} A group GG is called small if it has only finitely many subgroups of each index. Each small residually finite (r.f.)group is hopfian, namely, every epimorphism α ⁣:GG\alpha \colon G \to G is an isomorphism. (Proof: let VnV_n be the intersection of subgroups of index n\le n, and check that α(Vn)=Vn\alpha(V_n) = V_n for each nn.) If gkerαg \in \ker \alpha and g1g \neq 1 then g∉Vng \not \in V_n for some nn, so α(g)1\alpha(g) \neq 1 as well.)

Every f.g.\ profinite group is small and r.f., and hence hopfian. It follows that σ\sss above actually freely topologically generates GG.

A field LL is PAC (pseudo-algebraically closed) if every (irreducible) variety over LL has a point in LL. Besides algebraically closed fields, examples of PAC fields are the algebraic extensions LL of Fq\mathbb F_q with L:Fq=ω|L:\mathbb F_q| = \omega. See 15 for background. A field LL is ω\omega-free if Gal(L)\mathrm{Gal}(L) is topologically isomorphic to F^ω\hat F_\omega. \begin{thm}[Jarden, see Thms 18.6.1 and 27.4.8 in 15] Let G=Gal(Q)G = \mathrm{Gal}(\QQ) be the absolute Galois group of Q\QQ. For σ=(σ1,,σe)Ge\sss= (\sss_1, \ldots, \sss_e) \in G^e let Lσ=Q[σ]L_\sss=\QQ[\sss] denote the maximal Galois extension of Q\QQ contained in the fixed field of σ\sss; equivalently, LσL_\sss is the fixed field of the normal closure of σ\sss. For almost all tuples σ\sss, LσL_\sss is PAC and ω\omega-free. \end{thm}

Jarden and Lubotzky 25 study a related setting, namely G=F^nG= \hat F_n. \begin{thm}[Jarden and Lubotzky, Thm.\ 1.4 in 25] Let G=F^nG = \hat F_n for finite n2n\ge 2. For almost all tuples σ=(σ1,,σe)Ge\sss= (\sss_1, \ldots, \sss_e) \in G^e, the closed normal subgroup they topologically generate either has finite index or is a free profinite group of rank ω\omega. The second case holds for all σ\sss if e<ne\lt n, for almost all σ\sss if e=ne= n, and for a set of σ\sss with positive measure if e>ne>n. \end{thm}

The algorithmic theory

This section has benefitted from discussions with A.\ Melnikov.

Effectiveness conditions on profinite groups

\begin{definition}[Smith~41] \ \bi \item[(i)] A profinite group GG is called co-r.e. if it is the inverse limit of a computable inverse system Gn,pn\la G_n, p_n\ra of finite groups (i.e.\ the groups GnG_n and the maps pnp_n between them are uniformly computable). Equivalently, the subgroup UU above is a Π10\PI 1 subclass of nGn\prod_{n} G_n. \item[(ii)] GG is called computable if, in addition, the maps pnp_n can be chosen onto. In other words, the set of extendible nodes in the tree corresponding to UU is computable. \ei\end{definition}

Absolute Galois groups

Let KK be a computable field. Then the algebraic closure K\ol K has a computable presentation. (Qˉ\bar \QQ has a unique one, i.e.\ is autostable, by a result of Ershov.) Suppose in addition that KK has a splitting algorithm (for polynomials in one variable), i.e.\ one can decide whether a polynomial is irreducible. An example of such a field is Q\QQ. Then K\ol K has a computable presentation so that the KK viewed as a subset of K\ol K is decidable \cite[Lemma 6]{Rabin:60}. Also, the absolute Galois group of KK is computable. To show this, intuitively, one builds a computable chain K=L0L1K= L_0 \le L_1 \le \ldots of finite Galois extensions of KK with union Kˉ\bar K. The computable inverse system is given by the groups Gn=Gal(Ln/K)G_n = \mathrm{Gal}( L_n/K) where the projection pn ⁣:Gn+1Gnp_n \colon G_{n+1} \to G_n is given by restricting ϕGal(Ln+1/K)\phi \in \mathrm{Gal}( L_{n+1}/K) to LnL_n.

Computable profinite groups that are completions

Suppose GG is a computable group, and the class \+V\+ V in Definition~ ? is uniformly computable in that there is a uniformly computable sequence \seq{R_n} such that \+V={Rn ⁣:nN}\+ V = \{ R_n \colon n \in \NN \}. Suppose further that WW above can be obtained effectively from U,VU,V. Then there is a uniformly computable descending subsystem \seq {T_k} of \seq {R_n} such that nkTkRn\fa n \ex k \, T_k \le R_n. Since we can effectively find coset representatives of TnT_n in GG, the inverse system \seq {G/T_n} with the natural projections Tn+1aTnaT_{n+1} a \to T_n a is computable. So G\+VG_\+ V is computable. The criterion above is satisfied by FkF_k and FωF_\omega with the systems of normal subgroups introduced above. Thus their completions F^k\hat F_k and F^ω\hat F_\omega are computable profinite groups. \begin{lemma} Let GG be kk-generated (kωk \le \omega). Then GG is computable [co-r.e.] iff G=F^k/NG= \hat F_k/N for some computable normal subgroup NN (Π10\PI 1 N). \end{lemma}

Computability of Haar measure

We use the notion of a computable probability space by Hoyrup and Rojas 23. \begin{lemma} Let GG be computable profinite group. Then μG\mu_G, the Haar probability measure on GG, is computable. \end{lemma} \begin{proof} The inverse system Gn,pn\la G_n, p_n\ra is computable. So for a clopen set C=qn1(F)C=q_n^{-1}(F) as in Remark ?, given by the parameters nn and FF, we can compute the measure. This suffices. \end{proof} \begin{remark} Here is a more concrete description of the Haar measure. As before qn ⁣:GGnq_n \colon G \to G_n is the natural projection. We also assume that G1G_1 is trivial. We write V_n =\ker {q_n. For each nn we can effectively determine kn=Vn:Vn+1k_n = |V_n : V_{n+1}| and a sequence \seq{ g^{(n)}_{i}}_{i\lt k_n} of coset representatives for Vn+1V_{n+1} in VnV_n such that g0(n)=1g^{(n)}_0 = 1.

Let TT be the tree of strings σω<ω\sss \in \omega^{\lt \omega} such that σ(i)<ki\sss(i) \lt k_i for each i<σi\lt \sssl. For σ=n\sssl = n we have a coset of VnV_n in GG

Cσ=gσ(0)(0)gσ(1)(1)gσ(n1)(n1)Vn. C_\sigma = g^{(0)}_{\sss(0)} g^{(1)}_{\sss(1)} \ldots g^{(n-1)}_{\sss(n-1)} V_n.
The clopen sets CσC_\sss form a basis for GG. In this way GG is naturally homeomorphic to [T][T] where the identity element corresponds to 0ω0^\omega. The Haar measure is the usual uniform measure on [T][T]. }\end{remark}

Randomness notions defined via algorithmic tests

Let GG be a computable profinite group. Given that the Haar measure μ\mu on GG is computable, the usual randomness notions defined via algorithmic tests, or effectively descriptive set theory tests, can be applied. The usual question is: how strong a randomness notion on a group element gg suffices for an ``almost everywhere" properties to hold for gg? A point in a computable measure space is Kurtz random (or weakly random) if it is in no Π10\PI 1 null class. For Jarden's Thm.\ ?,and at least the first part of his Thm.\ ?, this rather weak randomness notion is sufficient. If the underlying topological space is effectively homeomorphic to Cantor space, then any weakly 1-generic point (i.e., in every dense Σ10\SI 1 set) is Kurtz random. As this applies to the setting of profinite groups at hand, the points for which Jarden's results hold are also comeager. \begin{thm}[effective form of Jarden's Thm.\ ? for Q\QQ] Let G=Gal(Q)G = \mathrm{Gal}(\QQ) be the absolute Galois group of Q\QQ. Let σ=(σ1,,σe)Ge\sss = (\sss_1, \ldots, \sss_e) \in G^e be Kurtz random. The closed subgroup generated by σ\sss is a free profinite group of rank ee (freely generated by σ\sss). \end{thm}

Here is a sketch why this is true. (For a full proof, thorough understanding of Jarden's result would be needed, which is hard work because of the long chain of dependencies and heavy notation leading up to \cite[18.5.6]{Fried.Jarden:06}.) All item numbers refer to 15.

Two extensions L1,L2L_1, L_2 of a common field KK (tacitly assumed to be contained in a common field) are called linearly disjoint if whenever a tuple from L1L_1 is linearly independent over KK, it remains linearly independent over L2L_2. By Lemma 2.5.1.\ this is symmetric.

A sequence of extensions L1,L2,L_1, L_2, \ldots is linearly disjoint if Lj+1L_{j+1} is l.d.\ from the compositum L1LjL_1 \ldots L_j for each jj. Given kk, Cor.\ 16.2.7.\ builds such a sequence of Galois extensions for K=QK= \QQ such that for each nn we have Gal(Ln/Q)Sk\mathrm{Gal}(L_n/ \QQ ) \cong S_k via some isomorphism ρn\rho_n. The sequence of fields \seq {L_n} is uniformly computable, as can be derived from the proof (hopefully).

By 18.5.1.\ the linear disjointness implies that the absolute Galois groups Gal(Ln)Gal(Q)\mathrm{Gal}(L_n)\le \mathrm{Gal}(\QQ) are μ\mu-independent; recall that μ\mu is the Haar measure on G=Gal(Q)G = \mathrm{Gal}(\QQ). More generally, by 18.5.2, for e1e \ge 1, if for each nn one picks a coset CnC_n of Gal(Ln)e\mathrm{Gal}(L_n)^e in GeG^e, the CnC_n are μe\mu^e-independent.

Now to conclude the argument, we want to show that each finite group RR generated by ee elements is a quotient of the closed subgroup σG\la \sss \ra \le G generated by σ\sss, as this suffices to show freeness. Embed RR into SkS_k for kk sufficiently large, and let π1,,πe\pi_1, \ldots, \pi_e be the images of the generators of RR under this embedding.

For each nn we have a natural onto homomorphism GGal(Ln/Q)G \to \mathrm{Gal}(L_n/\QQ) given by restriction to LnL_n (note that LnL_n, being a normal extension of Q\QQ, is preserved under automorphisms of Qˉ\bar \QQ). So we can effectively pick a coset CnC_n of Gal(Ln)e\mathrm{Gal}(L_n)^e in GeG^e that maps to π1,,πe\la \pi_1, \ldots, \pi_e \ra. Since the LnL_n are independent, these cosets are independent, and each has measure 1/(k!)e1/(k!)^e. Hence, by Borel-Cantelli their union has measure 11. The union is Σ10\SI 1 and hence contains the Kurtz random σ\sss. This shows that RR is a quotient of σ\la \sss \ra as required.

\begin{thm}[effective form of the first part of Jarden's Thm.\ ? for Q\QQ] In the setting of Thm. ?, recall that for an automorphism σGal(Q)\sss \in \mathrm{Gal} (\QQ), LσL_\sss is the fixed field of the normal closure of σ\sss. If σ\sss is Kurtz random, then LσL_\sss is PAC. \end{thm} \begin{proof} We first show that LσL_\sss is uniformly computable from (a code for) σ\sss. For xQx \in \ol \QQ to be in LσL_\sss, it suffices that each conjugate τ1στ\tau^{-1}\sss \tau fixes xx, or equivalently σ(y)=y\sss(y) = y for each yy in the orbit of xx under the action of Gal(Q)\mathrm{Gal}(\QQ). This orbit consists of all the conjugates of xx, and can be computed from xx.

By Jarden's theorem and the fact that a Kurtz random is in every Π20\PI 2 conull set, it now suffices to show that the PAC subfields KK of Q\ol \QQ form a Π20\PI 2 class.

Recall that for a unital ring RR, a nonconstant polynomial in R(X1,Xn)R(X_1, \to X_n) is called irreducible if it cannot be written as a product for two nonconstant polynomials. For a field KK, a polynomial in K[X1,,Xn]K[X_1, \ldots, X_n] is called absolutely irreducible if it is irreducible in K[X1,,Xn]\ol K[X_1, \ldots, X_n]. We use some facts on PAC fields from \cite[Section 11.3]{Fried.Jarden:06}. \cite[Theorem 11.2.3]{Fried.Jarden:06} implies:

\begin{prop} A field KK is PAC if and only if for every absolutely irreducible polynomial fK[X,Y]f \in K[X,Y], there is a point (a,b)K2(a,b) \in K^2 with f(a,b)=0f(a,b) = 0. \end{prop}

This yields the required Π20\PI 2 condition as soon as we can express using a Π10\PI 1 condition on the coefficients of ff that a polynomial fK[X,Y]f \in K[X,Y] is absolutely irreducible. But irreducibility of ff in the polynomial ring R[X1,,Xn]R[X_1, \ldots, X_n] is a Π10\PI 1 condition on the coefficients of ff for any computable ring RR, as one sees directly by inspecting the definition. \end{proof}

\begin{remark} The conditions (1) on page 200 in \cite[Section 11.3]{Fried.Jarden:06} yield a set of sentences in first-order logic expressing that a field is PAC. SK(2,d)S_K(2,d) denotes the set of polynomials fK(X,Y)f \in K(X,Y) of degree <d<d in both XX and YY. They say that for each irreducible hQ(T)h \in \QQ(T), some Π10\PI 1 condition holds (for each triple of polynomials g1,g2,g3)g_1, g_2, g_3) of bounded degree, something not involving quantifiers fails). It is decidable whether hh is irreducible as Q\QQ has a splitting algorithm, so we can also get a co-r.e.\ condition on coefficients in this way. \end{remark}

Potential generalisation to Hilbertian fields

A field KK is Hilbertian if every finite set of irreducible polynomials in a finite number of variables and having coefficients in KK admit a common specialization of a proper subset of the variables to field elements such that all the polynomials remain irreducible (Wikipedia). Hilbert showed that Q\QQ has this property (Hilbert's irreducibility theorem). All the classic a.e.\ theorems from 15 mentioned above are stated for any countable Hilbertian field, rather than just for Q\QQ. If KK is computable and has the effective splitting property, then one can expect that the effective versions hold as well.

18. Rute: On the computability of compact groups

This note covers basic theorems about the computability of Haar measures and profinite groups. The results are due to Jason Rute and were proved after discussions with Nies and Melnikov.

While we could work in the more general context of computable topological spaces, we will only focus here on computable metric spaces (also known as computably presented Polish spaces), since they are well understood.

Recall that a computable metric space X\mathbb{X} is a complete separable metric space (X,d)(X,d) along with a dense sequence of points (ai)(a_i) such that the map i,jd(ai,aj)i,j \mapsto d(a_i,a_j) is computable. We say X\mathbb{X} is effectively compact if one can enumerate all Σ10\Sigma^0_1 sets which cover X\mathbb{X}. It is easy to see that Cantor space is effectively compact. We will need the following well-known properties about effectively compact spaces.

\begin{prop} Let X\mathbb{X} be a computable metric space along with a computable sequence AnA_n where AnA_n is a list of points (a1n,,akn)(a^n_1, \ldots, a^n_k) such that every point in X\mathbb{X} is within distance 2n2^{-n} of some aina^n_i. Then X\mathbb{X} is effectively compact. \end{prop}

\begin{proof} Using the double sequence (ain)(a^n_i) we can construct a computable onto map f ⁣:2NXf \colon 2^\mathbb{N} \to \mathbb{X}. (The details are routine but a bit technical. A similar construction can be found in Simpson \cite[IV.1]{Simpson:09}.) Now, we want to enumerate all effectively open covers of X\mathbb{X}. That is the same as enumerating all empty Π10\Pi^0_1 subsets of X\mathbb{X}. Consider a Π10\Pi^0_1 set PXP \subseteq \mathbb{X}. The set f1(P)f^{-1}(P) is Π10\Pi^0_1 subset of 2N2^\mathbb{N}, and it is empty iff PP is empty. Since 2N2^\mathbb{N} is effectively compact we will enumerate f1(P)f^{-1}(P) eventually if it is empty, and then we can use that to enumerate PP. \end{proof}

\begin{prop} If X\mathbb{X} is an effectively compact computable metric space and {a}X\{a\} \subseteq \mathbb{X} is a Π10\Pi^0_1 singleton set, then aa is computable. If f ⁣:XXf \colon \mathbb{X} \to \mathbb{X} is a function whose graph fX×Xf \subseteq \mathbb{X} \times \mathbb{X} is Π10\Pi^0_1, then ff is computable. \end{prop}

\begin{proof} Let UU be the complement of {a}\{a\}. Compute aa by enumerating covers of the space of the form UBU \cup B where BB is a basic open ball of small radius. Similarly, use this method to compute f(x)f(x) from xx. \end{proof}

\begin{definition} A computable topological Polish group to be a computable metric space GG with a computable group operation and a computable inverse operation. ^2withtheEuclidean(with the Euclidean (\ell_2)metricandthe) metric and the\ell_\inftymetricareequivalentwithanynaturalchoiceofdenseset.ThenwecandefineacomputablePolishspaceasthesetofequivalenceclassesofcomputablemetricspaces.Similarly,wecanusethisideatogiveaslightlymorenaturaldefinitionofcomputablePolishgroup,againasequivalenceclasses.Thedownsideofthisapproachisthatweneedtoconstantlyshowthatthepropertiesweareinterestedinarepreservedbythisequivalencerelation.Forexample,iftwopresentationsofaspacemetric are equivalent with any natural choice of dense set. Then we can define a computable Polish space as the set of equivalence classes of computable metric spaces. Similarly, we can use this idea to give a slightly more natural definition of computable Polish group, again as equivalence classes. The downside of this approach is that we need to constantly show that the properties we are interested in are preserved by this equivalence relation. For example, if two presentations of a space\mathbb{X}areequivalent,andonepresentationiseffectivelycompact,thensoittheotherpresentation.Also,iftwopresentationsofare equivalent, and one presentation is effectively compact, then so it the other presentation. Also, if two presentations of\mathbb{X}areequivalent,thensoarethevariouscorrespondingpresentationsofthespaceofBorelprobabilitymeasuresonare equivalent, then so are the various corresponding presentations of the space of Borel probability measures on\mathbb{X}$. } \end{definition} The computable analogue of a compact group is a computable Polish group which is effectively compact.

\begin{fact} If GG is an effectively compact computable metric space with a computable group operation, then the inverse operation is also computable, and therefore GG is a computable Polish group. \end{fact}

\begin{proof} Notice that the graph of the inverse function {(g,g1)gG}\{(g, g^{-1}) \mid g \in G\} is a Π10\Pi^0_1 set. So the inverse map is computable by Proposition~ ?. \end{proof}

If X\mathbb{X} is a computable metric space, then the space of Borel probability measures on X\mathbb{X} is also a computable metric space. In particular, a Borel probability measure μ\mu is computable if and only if the map ffdμf \mapsto \int f d\mu is a computable map for all bounded computable functions f ⁣:XRf \colon \mathbb{X} \to \mathbb{R}. If X\mathbb{X} is effectively compact, then so is the space of Borel probability measures on X\mathbb{X}. For more on the computability of Borel probability measures, see Hoyrup and Rojas 22 or Bienvenu, Gacs, Hoyrup, Rojas, and Shen 2.

\begin{prop} Let GG be an effectively compact computable Polish group. Then the left and right Haar probability measures are computable. \end{prop}

\begin{proof} The set of, say, left Haar probability measures is a Π10\Pi^0_1 singleton set in the effectively compact space of Borel probability measures on X\mathbb{X}. By Proposition~ ? the left Haar measure is computable. \end{proof}

\begin{thm} Let GG be a compact computable Polish group for which the (left) Haar probability measure is computable. Then GG is effectively compact. \end{thm}

\begin{proof} We re-metrize the space GG by replacing d(x,y)d(x,y) with the average of d(gx,gy)d(gx,gy) where the average (the integral) is taken in the Haar measure as g varies across the group. This new metric is computable since d(x,y)d(x,y) is a bounded computable function. (The metric is bounded by the compactness of GG.) Now one has a computable GG-invariant distance which is equivalent to the original distance.

Now, to show that GG is effectively compact in this new metric, it is enough for each rational kk, to effectively find a finite set of points a0k,...,an1ka^k_0, ..., a^k_{n-1} for which every point in GG is within distance 2k2^{-k} of one of these points. Fix kk. Using our Haar measure find the measure of a ball of radius 2(k+1)2^{-(k+1)}. Call this measure δ\delta. (Since the new distance is GG-invariant, all balls of the same radius have the same measure.) Using blind search find a collection of balls B0,...,Bn1B_0, ..., B_{n-1} of balls with radius 2(k+1)2^{-(k+1)} whose union C=B0...Bn1C = B_0 \cup ... \cup B_{n-1} has measure >1δ\gt 1 - \delta. Now, consider any point xx not in this union CC. It has to be distance <2(k+1)\lt 2^{-(k+1)} from the union. Otherwise, there would be a ball centered at xx with radius 2(k+1)2^{-(k+1)}, and hence measure δ\delta, which is disjoint from the union CC. But the union CC has measure >1δ\gt 1 - \delta, so this cannot happen. Therefore all points of GG are within distance 2k2^{-k} of the centers of B0,...,Bn1B_0, ..., B_{n-1}. This algorithm shows that the space is effectively compact in the new metric. To show it is effectively compact in the original metric, for any finite list of rational balls in original metric, convert it to a list of balls in the new metric. Now, if this list of balls covers the space GG, by effective compactness, we will eventually find this out. \end{proof}

\begin{example} There is a computable group GG isomorphic to a product of finite cyclic groups ΠnGn\Pi_n G_n which is compact but for which the Haar measure is noncomputable. \end{example}

\begin{proof} Let h(n)h(n) be the characteristic function of the Halting set. Then we will let G=nZ2h(n)G = \prod_n \mathbb{Z}_{2^{h(n)}} with the ultrametric ρ(f,g)=inf{2nf(n)=g(n)}\rho(f,g) = \inf \{2^n \mid f(n) = g(n)\}. This is a computable metric space (but it is not effectively compact). It is also a computable Polish group. The Haar measure of any cylinder set of length nn is equal to k<n2h(n)\prod_{k<n} {2^{-h(n)}}. If we could compute the Haar measure, then we could compute h(n)h(n). \end{proof}

As Section~Section 4 in this year's Logic Blog mentioned, a profinite group is an inverse limit of finite groups. So there exists a descending chain of normal clopen subgroups NsGN_s \vartriangleleft G which converges to the identity. Then GG is the inverse limit of G/NsG/N_s. A GG is computably profinite.

\begin{thm} Let GG be a profinite effectively compact computable Polish group. Then we can compute a sequence of finite groups GsG_s such that GG is the inverse limit GsG_s and the corresponding homomorphism hs ⁣:GGsh_s \colon G\to G_s is computable. \end{thm}

\begin{proof} Since GG is profinite, we need to find a descending chain of normal clopen subgroups NsGN_s \vartriangleleft G. Since GG is effectively compact, we can enumerate all clopen sets AA by finding disjoint covers made up of finitely many open balls B1,Bn,C1,,CmB_1, \ldots B_n, C_1, \ldots, C_m where BiB_i and CjC_j are disjoint. We can then use this to enumerate all normal clopen subgroups as follows. Since each clopen set AA is both effectively open and closed, the property \[\forall g\in G\quad gAg^{-1} \subseteq A\] is Π10\Pi^0_1 (if the property fails, then search for some gGg\in G and some aAa\in A such that gag1gag^{1} is outside of AA) and Σ10\Sigma^0_1 (if the property holds, then wait for an enumeration of balls which cover gAg1gAg^{-1} and which are disjoint from a cover of the complement of AA). Therefore, we can enumerate all clopen normal subgroups NGN \vartriangleleft G.

Let NsN_s be the intersection of all clopen normal subgroups enumerated at stage ss of the construction (where N0=GN_0 = G). This is also a clopen normal subgroup. Now enumerate all cosets gNsgN_s. (These can be enumerated since each coset gNsgN_s is also clopen. Also we know when we have enumerated them all since they form an open cover of an effectively compact space.) From this we can compute G/NsG/N_s along with the corresponding homomorphism. (If GG is finite, then at some stage, G/NsG/N_s is isomorphic to GG.) \end{proof} \part{Metric spaces and descriptive set theory}


19. Nies and Weiss: \\ complexity of topological isomorphism for subshifts

Let Σ\Sigma be a finite alphabet. A subshift is a closed subset XΣZX \sub \Sigma^ \ZZ which is invariant under the shift σ\sss. We consider the complexity of the isomorphism relation (X,σX)(Y,σY)(X, \sss_X) \cong (Y, \sss_Y) where Σ,Δ\Sigma,\Delta are finite alphabets and XΣZX \sub \Sigma ^ \ZZ, YΔZY \sub \Delta ^ \ZZ are subshifts. To be isomorphic means that there is a continuous bijection θ:XY\theta: X \to Y such that θ(σX(z))=σY(θ(z))\theta (\sss_X(z) ) = \sss_Y( \theta(z)) for each zXz \in X. Note that θ\theta is given by the clopen sets θ1({Z ⁣:Z(0)=b})\theta^{-1}(\{ Z \colon \, Z(0)=b\}) for bΔb \in \Delta, which are of the form i<k[αi]\bigcup_{i<k} [\alpha_i] where αi:[N,N]Σ\alpha_i: [-N, N] \to \Sigma (such a collection of clopen sets is called a block code). So isomorphism is a countable Borel equivalence relation.

J.\ Clemens (Israel J. of Maths, 2009) proved that isomorphism is in fact a B\le_B-complete countable Borel equivalence relation. A subshift is minimal if every orbit of an element is dense; equivalently, every possible pattern (i.e.\ subword of a fixed length of an element of the subshift) occurs in a large enough section of every element of the subshift. By compactness, the length of this section only depends on the pattern. As a consequence, minimality is a Borel property of subshifts. Also, it is sufficient to require the property that patterns re-occur within a distance only dependent on the pattern for one word with dense orbit. Clemens asked in the paper and in a 2014 talk (available on youtube) the following question:

\begin{question} How complex is the isomorphism relation between minimal subshifts? \end{question} Gao, Jackson and Seward \cite[Section 9.3]{Gao.Jackson.etal:16} proved that E0E_0 is Borel reducible to isomorphism of minimal subshifts. \begin{proof} Here is a sketch of a short proof of this fact. The idea is to build a sequence of blocks An,Bn{A_n, B_n} of length Ln=(66)nL_n = (66)^{n}. The construction is controlled by a fixed element x{0,1}Nx \in \{0,1\}^\NN with the n-stage blocks a function of xix_i for 1in1 \leq i \leq n. This sequence of blocks determines a subshift SxS_x: the allowed patterns of length LnL_n are the AnA_n and BnB_n.

The blocks An+1,Bn+1{A_{n+1}, B_{n+1}} will be built out of the n-stage blocks in such a way that any bi-infinite sequence formed by concatenating these two blocks has a unique parsing into blocks of these two types. This parsing defines for each bi-infinite word \seq {z(i)}_{i \in \ZZ} a unique integer modulo LnL_n which indicates the position of z(0) in the block. Recall that an odometer is a dynamical system that is an inverse limit of periodic rotations. The simplest example is the 22-adic integers with addition by 11. Since Ln+1L_{n+1} is a multiple of LnL_n, the position of z(0)z(0) modulo Ln+1L_{n+1} when reduced modulo LnL_n gives the position of z(0)z(0) in its ``n-block". This will yield a common odometer as a factor of all the minimal shifts.

Let A0=0A_0 = 0 and B0=1B_0 = 1. We describe 4 recipes for concatenating A,B{A,B}:

\bi \item[1.] AB(A4B4)8AB(A^4B^4)^8

\item[2.] AB(A8B8)4AB(A^8B^8)^4

\item [3.] AB(A16B16)2AB(A^{16}B^{16})^2

\item [4.] ABA32B32AB{A^{32}B^{32}}. \ei

\n Depending upon the value of xnx_{n} the An+1,Bn+1{A_{n+1}, B_{n+1}} will be formed in two different ways. If xn+1=1x_{n+1}=1 one uses 1 and 2, otherwise one uses 3 and 4. Assuming that one can recognize A and B, the initial ABA in all recipes guarantees that the concatenations have a unique parsing.

The minimality is immediate since all four possibilities AA, AB, BA, BB occur.

Each specfic minimal system has its own collection of the two types of blocks, where the nature of the blocks up to level n depend only on the first n bits of the control element from 0,1N{0,1}^\NN. Clearly if x and y agree from some point on there is a finite block code that will map one shift to the other. If x and y differ infinitely often then no matter what the length of the code eventually it will pick up the pattern of repetitions which differ significantly in all 4 recipes. \end{proof}

Simon Thomas 42 has given a Borel reduction of E0E_0 to a special class of minimal subshifts, the Toeplitz subshifts. A Toeplitz word is a bi-infinite word WW such that for nZn\in \ZZ there is a ``local period" kZk\in \ZZ such that iZ[W(n)=W(n+ik)]\fa i\in \ZZ \, [W(n) = W(n+ik)]. A subshift is Toeplitz if it contains a Toeplitz word with dense orbit. To see that this is minimal, suppose that ww is a subword of WW, and let rr be the l.c.m.\ of the local periods of any symbol in ww. Then σr(w)\sigma^r(w) is also a subword of WW, for any rZr \in \ZZ.

Not much beyond that is known so far on the complexity of conjugacy for minimal subshifts.

\part{Higher computability theory/effective descriptive set theory}


20. Yu: $\Pi^1_1$-hyperarithmetic determinacy

Input by Yu.

The following theorem was claimed in 21: the hyperdegrees of a Π11\Pi^1_1 set with a perfect subset contain an upper cone. \begin{theorem}[Harrington 21] Let A2ωA\subseteq 2^{\omega} is a Π11\Pi^1_1 set that contains a perfect subset. There is a real z2ωz\in 2^{\omega} so that for any real yhzy\geq_h z, there is a real xAx\in A for which xhyx\equiv_h y. \end{theorem}

The following proof is based on some communications with Leo Harrington. His original idea seem model theoretical. Here is a tree proof.

The following theorem is proved by Martin. \begin{theorem}[Martin 28] If AA is an uncountable Δ11\Delta^1_1-set, then for any real yhOy\geq_h \KO, there is a real xAx\in A for which xhyx\equiv_h y. \end{theorem}

Fix an uncountable Π11\Pi^1_1 set AA throughout in this section. Since AA is Π11\Pi^1_1, there is a recursive oracle functional Φ\Phi so that

̲\omega." style="color:#cc0000">x\in A \Leftrightarrow \Phi^x codes a well ordering of ω\omega.

In other words, the binary relation nxmn\leq_x m if and only if Φx(n,m)=1\Phi^x(\langle n,m\rangle)=1 is a well ordering over ω\omega. We use nDom(Φx)n\in Dom(\Phi^x) to denote that there is some mm so that Φx(n,m)=1\Phi^x(\langle n,m\rangle)=1 or Φx(m,n)=1\Phi^x(\langle m,n\rangle)=1. For a finite binary string σ\sigma, we also use <Φσ\lt _{\Phi^{\sigma}} to denote the finite linear order coded by Φσ\Phi^{\sigma}.

Let

̲\omega with or…" style="color:#cc0000">\beta=\min\{\beta\mid |\{ x \mid \Phi^x codes a well ordering of ω\omega with order type \beta\}|\gt \aleph_0\}.

Since AA has a perfect subset, such β\beta must exist.

We fix the β\beta throughout.

We associate a tree TT with AA by defining (σ,τ)T(\sigma,\tau)\in T if and only if 1. σ2<ω\sigma \in 2^{\lt \omega} and; 2. τ\tau is finite order preserving function from Dom(Φσ)Dom(\Phi^{\sigma}) to ordinals.

We always assume that Dom(Φσ)=σ|Dom(\Phi^{\sigma})|=|\sigma|.

(σ0,τ0)(σ1,τ1)(\sigma_0,\tau_0)\preceq (\sigma_1,\tau_1) if both σ1\sigma_1 and τ1\tau_1 extends σ0\sigma_0 and τ0\tau_0 respectively. (σ0,τ0)(\sigma_0,\tau_0) is at the left of (σ0,τ0)(\sigma_0,\tau_0) if 1. for some are mmin{σ0,σ1}m\leq \min\{|\sigma_0|,|\sigma_1|\}, σ0m=σ1m\sigma_0\uh m=\sigma_1\uh m but σ0(m+1)<σ1(m+1)\sigma_0(m+1)\lt \sigma_1(m+1) or 2. for every $\sigma_0\uh \min\{|\sigma_0|,|\sigma_1|\}=\sigma_1 \uh \min\{|\sigma_0|,|\sigma_1|\}andforsomeand for somek$, τ0(k)<τ1(k)\tau_0(k)\lt \tau_1(k) but τ0(j)=τ1(j)\tau_0(j)=\tau_1(j) for all j<Φσkj\lt _{\Phi^{\sigma}}k.

Then xAx \in A if and only if there is an ff so that (x,f)(x,f) is an infinite branch of TT.

Let TβT^{\beta} be the tree TT restricted to the ordinal β\beta, i.e. the range of every σ\sigma is a subset β+1\beta+1. Obviously TβLω1βT^{\beta}\in L_{\omega_1^{\beta}}. Moreover, there are uncountable many infinite branches in TβT^{\beta} by the definition of β\beta. Let

̲\omega of orde…" style="color:#cc0000">A_{\beta}=\{x\mid \Phi^x codes a well ordering of ω\omega of order type \leq\beta\}.

Then AβA_{\beta} is exactly the collection of reals xx for which there is an ff so that (x,f)(x,f) is an infinite branch through TβT^{\beta}.

Obviously AβA_{\beta} is an uncountable Borel set containing a perfect subset.

Let ω1β\omega_1^{\beta} be the least admissible ordinal greater than β\beta. Obviously TβLω1βT^{\beta}\in L_{\omega_1^{\beta}}.

Case(1): There is a real zz so that z\in L_{\omega_1^{\beta} and ω1z=ω1β\omega_1^z=\omega_1^{\beta}.}

Then let $B_{\beta}=\{x\mid \Phi^x codes a well ordering of order type \beta\}\subseteq A_{\beta}beabe a\Delta^1_1(z)set.Thenforanyreal-set. Then for any realx\in B_{\beta},,x\geq_h z.RelativizingtheproofofTheorem?to. Relativizing the proof of Theorem ? toz$, we may have Theorem ?.

Case(2): Otherwise.

Then for any real xAβx\in A_{\beta}, if Φx\Phi^x codes a well ordering of β\beta, then x∉Lω1βx\not\in L_{\omega_1^\beta}.

Fix a recursive enumeration of set theoretical Σ0\Sigma_0-formulas {φi(u,v,β)}iω\{\varphi_i(u,v,\beta)\}_{i\in \omega} with β\beta as a parameter. Then ω1β\omega_1^{\beta} is the least ordinal γ>β\gamma>\beta so that for any ii,

Lγu<βvφi(u,v,β)wu<βvLwφi(u,v,β).L_{ \gamma}\models \forall u\lt \beta\exists v \varphi_i(u,v,\beta)\rightarrow \exists w\forall u\lt \beta\exists v\in L_{w} \varphi_i(u,v,\beta).

We also do a Cantor-Bendixon derivation to TβT^{\beta}. I.e. T0β=TβT_{0}^{\beta}=T^{\beta}; and for any stage γ<ω1β\gamma\lt \omega_1^{\beta} and (σ1,τ1)(σ0,τ0)Tγβ(\sigma_1,\tau_1)\succ (\sigma_0,\tau_0)\in T_\gamma^{\beta}, if 1. either there exists an order preserving (in the <KB\lt _{KB} sense ) function fLβf \in L_{\beta} so that f:T1β[(σ1,τ1)]βf: T_1^{\beta}[(\sigma_1,\tau_1)]\to \beta; or 2. there exists a real xLβx\in L_{\beta} so that {x}={zσ1fτ1n(xn,fn)Tγβ}\{x\}=\{z\succ \sigma_1\mid \exists f \succ \tau_1\forall n(x\uh n, f\uh n)\in T^{\beta}_{\gamma}\}, then we let T1β+1=T1β[(σ1,τ1)]T_1^{\beta+1}=T_1^{\beta}\setminus [(\sigma_1,\tau_1)] and claim that (σ1,τ1)(\sigma_1,\tau_1) is cut off from TγβT_\gamma^{\beta} at stage γ\gamma. If γ\gamma is a limit stage, then Tγβ=γ<γTγβT_{\gamma}^{\beta}=\bigcap_{\gamma'\lt \gamma}T_{\gamma'}^{\beta}. Let

Tω1ββ=γ<ω1βTγβ.T_{\omega_1^{\beta}}^{\beta}=\bigcap_{\gamma\lt \omega_1^{\beta}}T_{\gamma}^{\beta}.

Obviously Tω1ββT_{\omega_1^{\beta}}^{\beta} is not empty. Let T12ω×ω<ωT^1\subseteq 2^{\omega}\times \omega^{\lt \omega} be a recursive tree so that p[T1]={xf(x,f)[T1]}={xx∉Lω1x}p[T^1]=\{x\mid \exists f (x,f)\in [T^1]\}=\{x\mid x\not\in L_{\omega_1^x}\}.

Since AβA_{\beta} contains a perfect subset, p[T1]Aβp[T^1]\cap A_{\beta}\neq \emptyset.

\begin{lemma}If xp[T1]Aβx\in p[T^1]\cap A_{\beta}, then x∉Lω1βx\not\in L_{\omega_1^{\beta}} and ω1xω1β\omega_1^x\geq \omega_1^{\beta}. Moreover, if Φx\Phi^x codes a well ordering of order type less than β\beta, then xLω1xx\in L_{\omega_1^x} and ω1xω1β\omega_1^x\leq \omega_1^{\beta}. \end{lemma} \begin{proof} Fix a real xAβx\in A_{\beta}.

If Φx\Phi^x codes a well ordering of order type β\beta, then ω1xω1β\omega_1^x\geq \omega_1^{\beta}. So x∉Lω1βx\not\in L_{\omega_1^{\beta}}.

If Φx\Phi^x codes a well ordering of order type γ\gamma less than β\beta, then AγA_{\gamma} is a countable set which is Δ11(z)\Delta^1_1(z) for any real zz with ω1zγ\omega_1^z\geq \gamma. Then xhzx\leq_h z for any real zz with ω1zω1γ\omega_1^z\geq \omega_1^{\gamma}. But ω1xω1γ\omega_1^x\geq \omega_1^{\gamma}. So xLω1γx\in L_{\omega_1^{\gamma}} and ω1γ=ω1x\omega_1^{\gamma}=\omega_1^x. Hence x∉p[T1]x\not\in p[T^1]. \end{proof}

So if xp[T1]Aβx\in p[T^1]\cap A_{\beta}, then x>hOx>_h \KO.

Let

T2=T1Tβ={(σ0,σ1,σ2)(σ0,σ1)T1(σ0,σ2)Tβ}.T^2=T^1\otimes T^{\beta}=\{(\sigma_0,\sigma_1,\sigma_2)\mid (\sigma_0,\sigma_1)\in T^1 \wedge (\sigma_0,\sigma_2)\in T^{\beta}\}.

Obviously T2Lω1βT^2\in L_{\omega_1^\beta{}} and [T2][T^2] is not empty. Let (x,f,h)(x,f,h) be the leftmost infinite path through T2T^2. Then xp[T1]Aβx\in p[T^1]\cap A_{\beta} and so by Lemma ?, xLω1β+2Lω1βx\in L_{\omega_1^{\beta}+2}\setminus L_{\omega_1^{\beta}}. In other words, there must be a master code in Lω1β+2Lω1βL_{\omega_1^{\beta}+2}\setminus L_{\omega_1^{\beta}}.

Fix a standard master code z_0 \in L_{\omega_1^{\beta+2}\setminus L_{\omega_1^{\beta}}}.

Now let y0>hz0y_0\gt _h z_0 be a real.

\begin{definition}

Given a tree S2<ω×α<ωS\subset 2^{\lt \omega}\times \alpha^{\lt \omega} where α\alpha is an ordinal, a finite pair (σ,τ)S(\sigma,\tau)\in S is called a splitting node in SS if for any i1i\leq 1, there is some γi\gamma_i so that (σi,τγi)S(\sigma^{\smallfrown}i,\tau^{\smallfrown}\gamma_i)\in S.

\end{definition}

\begin{definition} Given an infinite path (x,f)[Tω1ββ](x,f)\in [T_{\omega_1^{\beta}}^{\beta}], a number nn and an ordinal γω1β\gamma\leq \omega_1^{\beta}, we say that γ\gamma is correct up to nn respect to (x,f)(x,f) if for any ini\leq n, (xi,fi)(x\uh i,f\uh i) is a splitting node in Tω1ββT_{\omega_1^{\beta}}^{\beta} if and only if (xi,fi)(x\uh i,f\uh i) is a splitting node in TγβT_{\gamma}^{\beta}. \end{definition} The following lemma is clear. \begin{lemma} Suppose that (x,f)[Tω1ββ](x,f)\in [T_{\omega_1^{\beta}}^{\beta}], nn is a number and γγω1β\gamma\leq \gamma'\leq \omega_1^{\beta}. If γ\gamma is correct up to nn respect to (x,f)(x,f), the so is γ\gamma'. \end{lemma} The following definition is crucial to the proof. Intuitively we use even parts to code y0y_0 so that we may find a very large stage at which we may witness whether φi(u,v,β)\varphi_{i}(u,v,\beta) can be satisfied. However we use the odd parts to indicate when the coding stage is finished. \begin{definition}Given a finite pair (σ,τ)Tω1ββ(\sigma,\tau)\in T_{\omega_1^{\beta}}^{\beta}, let (x_{\sigma,f_{\tau })\in [T_{\omega_1^{\beta}}^{\beta}[\sigma,\tau]]} be an infinite path satisfying the following properties: - If fτ(n)f_{\tau }\uh (n) is the least ordinal γ\gamma so that [Tω1ββ[xσn+1,fτnγ]][T_{\omega_1^{\beta}}^{\beta}[x_{\sigma}\uh n+1 ,f_{\tau }\uh n^{\smallfrown }\gamma]]\neq \emptyset; and - If nn is the 2k2k-th number (in the natural ordering sense) for some k>0k>0 in SPσ,τ={j(xσj,fτj)[Tω1ββ[σ,τ]]isasplittingnode}SP_{ \sigma, \tau }=\{j\mid (x_{\sigma}\uh j,f_{\tau }\uh j)\in [T_{\omega_1^{\beta}}^{\beta}[\sigma,\tau]] is a splitting node\}, then xσ(n+1)=xσ(n)y0(k)x_{\sigma }(n+1)=x_{\sigma }(n)^{\smallfrown}y_0(k); and - If nn is the 2k+12k+1-th number for some k0k\geq 0 in SPσ,τSP_{ \sigma, \tau }, then xσ(n+1)=xσ(n)0x_{\sigma }(n+1)=x_{\sigma }(n)^{\smallfrown}0. \end{definition} Obviously given any number nn and pair (σ,τ)Tω1ββ(\sigma,\tau)\in T_{\omega_1^{\beta}}^{\beta}, (xσ,fτ)(x_{\sigma },f_{\tau }) always exists and fτLmax{ω1x,ω1β}[x]f_{\tau} \in L_{\max\{\omega_1^x , \omega_1^{\beta}\}}[x]. \begin{lemma} Φxσ\Phi^{x_{\sigma }} codes a well ordering of ω\omega with order type β\beta. \end{lemma} \begin{proof} Otherwise, by Lemma ?, xLβx\in L_{\beta}. So by a zig-zag decoding argument over Tω1ββT_{\omega_1^{\beta}}^{\beta}, y0xz0hz0y_0\leq x\oplus z_0\equiv_h z_0, a contradiction. \end{proof} \begin{lemma} If there is a pair (σ,τ)Tω1ββ(\sigma,\tau)\in T_{\omega_1^{\beta}}^{\beta} and some stage γ<ω1β\gamma\lt \omega_1^{\beta} so that for any nn, γ\gamma is correct up to nn respect to (xσ,fτ)(x_{\sigma },f_{\tau }), then xσhy0x_{\sigma }\equiv_h y_0. \end{lemma} \begin{proof} By the property of (xσ,fτ)(x_{\sigma },f_{\tau }), fτLω1xσ[xσ]f_{\tau }\in L_{\omega_1^{x_{\sigma }}}[x_{\sigma }]. We claim that ω1βω1xσ\omega_1^{\beta}\leq \omega_1^{x_{\sigma }}. Otherwise, by Lemma ?, xσLβx_{\sigma}\in L_{\beta}. By by a zig-zag coding over Tγβ[σ,τ]T_{\gamma}^{\beta}[\sigma,\tau], we have that y0Lω1β[xσ]=Lω1βy_0\in L_{\omega_1^{\beta}}[x_{\sigma}]=L_{\omega_1^{\beta}} , a contradiction to the choice of y0y_0. So γ<ω1βω1xσ\gamma\lt \omega_1^{\beta}\leq \omega_1^{x_{\sigma }}. Then it is clear that, by a zig-zag decoding over Tγβ[σ,τ]T_{\gamma}^{\beta}[\sigma,\tau], we may decode y0y_0 by (xσ,fτ)(x_{\sigma }, f_{\tau }). So y0hxσy_0\leq_h x_{\sigma }. Obviously y0hxσy_0\geq_h x_{\sigma }. So xσhy0x_{\sigma }\equiv_h y_0. \end{proof} So if the assumption of Lemma ? holds, then the proof of Theorem ? is finished. \bigskip From now on, we assume for any pair (\sigma,\tau)\in T_{\omega_1^{\beta}^{\beta} and any ordinal γ<ω1β\gamma\lt \omega_1^{\beta}, there is some number nn so that γ\gamma is not correct up to nn respect to (xσ,fτ)(x_{\sigma },f_{\tau }).} \bigskip Now we turn to the real construction. We will construct an infinite path (x,f)Tω1ββ(x,f)\in T_{\omega_1^{\beta}}^{\beta} so that y0hxy_0\equiv_h x. To code y0y_0, we use a zig-zag coding which is performed in Lω1β+1L_{\omega_1^{\beta}+1}. So the point is show ω1x>ω1β\omega_1^x>\omega_1^{\beta}. We start to construct (x,f)(x,f) by induction on ω\omega. At stage 00. Let (σ00,σ01)=(,)Tω1ββ(\sigma_0^0,\sigma^1_0)=(\emptyset,\emptyset)\in T_{\omega_1^{\beta}}^{\beta}. At stage s+1s+1. Suppose that (σs0,σs1)Tω1ββ(\sigma_s^0,\sigma^1_s)\in T_{\omega_1^{\beta}}^{\beta} has been constructed so that (σs0,σs1)(\sigma_{s}^0,\sigma^1_{s}) is a splitting node in Tω1ββT_{\omega_1^{\beta}}^{\beta} (Without loss of generality, we may assume that (,)(\emptyset,\emptyset) is a splitting node in Tω1ββT_{\omega_1^{\beta}}^{\beta}.). Substage (1): We code y0(s)y_0(s) at this substage. Let σs,10\sigma_{s,1}^0 be the shortest finite string so that there is a string σs,11\sigma^1_{s,1} such that - [(1)] (σs,10,σs,11)Tω1ββ(\sigma_{s,1}^0,\sigma^1_{s,1})\in T_{\omega_1^{\beta}}^{\beta} is a splitting node; and - [(2)] σs,10(σs0)y0(s)\sigma_{s,1}^0\succeq (\sigma_s^0)^{\smallfrown}y_0(s); and - [(3)] (σs,10,σs,11)(\sigma_{s,1}^0,\sigma^1_{s,1}) is the leftmost string in {(σs,10,τ)(σs,10,τ)Tω1ββ}\{(\sigma_{s,1}^0,\tau)\mid (\sigma_{s,1}^0,\tau)\in T_{\omega_1^{\beta}}^{\beta}\}. Obviously such a pair (σs,10,σs,11)(\sigma_{s,1}^0,\sigma^1_{s,1}) exists.

Substage(2): We try to make sure ω1x>ω1β\omega_1^x>\omega_1^{\beta} at this stage. Let (xσs,10,fσs,11)Tω1ββ[σs,10,σs,11](x_{\sigma_{s,1}^0}, f_{\sigma^1_{s,1}}) \in T_{\omega_1^{\beta}}^{\beta}[\sigma_{s,1}^0,\sigma^1_{s,1}] be as defined in Definition ?.

Case(2.1). Lω1βu<βvφi(u,v,β)L_{\omega_1^{\beta}}\models \forall u\lt \beta\exists v \varphi_i(u,v,\beta). Then let γs\gamma_s be the least ordinal so that u<βvLγsφi(u,v,β)\forall u\lt \beta\exists v\in L_{\gamma_s} \varphi_i(u,v,\beta). Then by the assumption, we may let nsn_{s} be the least number nn so that - (xσs,10n,fσs,11n)(x_{\sigma_{s,1}^0}\uh n, f_{\sigma^1_{s,1}}\uh n) is a splitting node in Tω1ββT_{\omega_1^{\beta}}^{\beta}; and - nn is the 2k+12k+1-th number for some k0k\geq 0 in SPσs,10,σs,11={j(xσs,10j,fσs,11j)Tω1ββ[σs,10,σs,11]isasplittingnode}SP_{\sigma_{s,1}^0,\sigma^1_{s,1}}=\{j\mid (x_{\sigma_{s,1}^0}\uh j, f_{\sigma^1_{s,1}}\uh j) \in T_{\omega_1^{\beta}}^{\beta}[\sigma_{s,1}^0,\sigma^1_{s,1}] is a splitting node\}; - γs\gamma_s is not correct up to nn respect to (xσs,10,fσs,11)(x_{\sigma_{s,1}^0}, f_{\sigma^1_{s,1}}). Then let (σs+10,σs+11)(\sigma_{s+1}^0, \sigma^1_{s+1}) be a finite string such that - [(1)] (σs+10,σs+11)Tω1ββ(\sigma_{s+1}^0,\sigma^1_{s+1})\in T_{\omega_1^{\beta}}^{\beta} is a splitting node extending (xσs,10ns,fσs,11ns)( x_{\sigma_{s,1}^0}\uh n_s, f_{\sigma^1_{s,1}}\uh n_s); and - [(2)] σs+10xσs,10ns1\sigma_{s+1}^0\succeq x_{\sigma_{s,1}^0}\uh n_s^{\smallfrown}1 (we use this to indicate the coding construction at this stage is finished); and - [(3)] (σs+10,σs+11)(\sigma_{s+1}^0,\sigma^1_{s+1}) is the leftmost string satisfying above property. Case(2.2). Otherwise. Then there is some u<βu\lt \beta so that Lω1βv¬φi(u,v,β)L_{\omega_1^{\beta}}\models \forall v \neg\varphi_i(u,v,\beta). Then by the assumption, let nsn_{s} be the least number nn so that - (xσs,10ns,fσs,11n)(x_{\sigma_{s,1}^0}\uh n_s, f_{\sigma^1_{s,1}}\uh n) is a splitting node in Tω1ββT_{\omega_1^{\beta}}^{\beta}; and - There is some dDom(Φxσs,10n)d\in Dom(\Phi^{x_{\sigma_{s,1}^0}\uh n}) so that fσs,11n(d)=uf_{\sigma^1_{s,1}}\uh n(d)=u (remember that fσs,11nf_{\sigma^1_{s,1}}\uh n is a finite order preserving function from Dom(Φxσs,10n)Dom(\Phi^{x_{\sigma_{s,1}^0}\uh n}) to β\beta); and - nn is the 2k+12k+1-th number for some k0k\geq 0 in SPσs,10,σs,11SP_{\sigma_{s,1}^0,\sigma^1_{s,1}}; Since Φxσs,10\Phi^{x_{\sigma_{s,1}^0}} codes a well ordering of order type β\beta, such a number nsn_s must exist. Then let (σs+10,σs+11)(\sigma_{s+1}^0,\sigma^1_{s+1}) be a finite string such that - [(1)] (σs+10,σs+11)Tω1ββ(\sigma_{s+1}^0,\sigma^1_{s+1})\in T_{\omega_1^{\beta}}^{\beta} is a splitting node extending (xσs,10ns,fσs,11ns)( x_{\sigma_{s,1}^0}\uh n_s, f_{\sigma^1_{s,1}}\uh n_s); and - [(2)] σs+10xσs,10ns1\sigma_{s+1}^0\succeq x_{\sigma_{s,1}^0}\uh n_s^{\smallfrown}1 (we use this to indicate the coding construction at this stage is finished); and - [(3)] (σs+10,σs+11)(\sigma_{s+1}^0,\sigma^1_{s+1}) is the leftmost string satisfying above property. This finishes the coding construction at stage s+1s+1.

\bigskip

Let

(x,f)=sω(σs0,σs1).(x,f)=\bigcup_{s\in \omega}(\sigma_{s}^0,\sigma^1_{s}).

By the construction, ff is an automorphism between Φx\Phi^x and an initial segment of ω1x\omega_1^x. By the same proof of Lemma ?, Φx\Phi^x codes a well ordering of ω\omega with order type β\beta and so ω1xω1β\omega_1^x\geq \omega_1^{\beta}. Hence ff is an automorphism between Φx\Phi^x and β\beta. We use a method in 44 to decode the coding construction. We shall xx-hyperarithmetically construct an increasing sequence ordinals {αi}\iω\{\alpha_i\}_{\i\in \omega} so that limiαi=ω1β\lim_i \alpha_i=\omega_1^{\beta}. Then ω1x>ω1β\omega_1^x>\omega_1^{\beta}. Once this is archived, then by a zig-zag decoding, we have that xhy0x\geq_h y_0 and so xhy0x\equiv_h y_0. \begin{definition}Given a finite increasing sequence {ni}is\{n_i\}_{i\leq s} for some ss and an ordinal γ<ω1β\gamma\lt \omega_1^{\beta}, we say that γ\gamma matches {ni_is\{n_i\_{i\leq s}} if all the following facts hold: - n0=0n_0=0; and - For any lnsl\leq n_s, (xl,fl)(x\uh l,f\uh l) is the leftmost in {(xl,τ)(xl,τ)Tγβ}\{(x\uh l,\tau)\mid (x\uh l,\tau)\in T_{\gamma}^{\beta}\}; and - For any j(0,s]j\in (0,s], \begin{itemize} - There is a number l0l_0 which is the least number greater than nj1n_{j-1} so that (xl0,fl0)(x\uh l_0,f\uh l_0) is splitting node in TγβT^{\beta}_{\gamma}; and - (xl0,fl0)(x\uh l_0,f\uh l_0) is the leftmost finite string in {(xl0,τ)(xl0,τ)Tγβ}\{(x\uh l_0,\tau)\mid (x\uh l_0,\tau)\in T_{\gamma}^{\beta}\}; and - There is a number l1>l0l_1\gt l_0 so that (xl1,fl1)(x\uh l_1, f\uh l_1) is the 2k+12k+1-th number, for some kk, in SPxl0,fl0={j(xj,fj)Tγβ[xl0,fl0]isasplittingnode}SP_{ x\uh l_0,f\uh l_0}=\{j\mid (x \uh j, f \uh j) \in T_{\gamma}^{\beta}[x\uh l_0,f\uh l_0] is a splitting node\} so that xxl11x\succ x\uh l_1^{\smallfrown}1; and - Either Lω1βu<βvLγφi1(u,v,β)L_{\omega_1^{\beta}}\models \forall u\lt \beta\exists v\in L_{\gamma} \varphi_{i-1}(u,v,\beta) or there is some dDom(Φxl1)d\in Dom(\Phi^{x\uh l_1}) so that Lω1βvLγ¬φi1(f(d),v,β)L_{\omega_1^{\beta}}\models \forall v\in L_{\gamma} \neg \varphi_{i-1}(f(d),v,\beta); and - njn_j is the least number greater than l1l_1 so that (xnj,fnj)(x\uh n_j, f\uh n_j) is a splitting node in TγβT_{\gamma}^{\beta}. \end{itemize} \end{definition} Intuitively if γ\gamma matches {ni}is\{n_i\}_{i\leq s}, then, up to nsn_s, TγβT_{\gamma}^{\beta} is ``quite like Tω1ββT_{\omega_1^{\beta}}^{\beta} along (x,f)(x,f)". \bigskip Now we start to do the decoding construction. At stage 00, let α0=0\alpha_0=0 and n00=0n_0^0=0. Claim that 00 is inactive, ii is active and ni0n_i^0 is undefined for any i>0i>0.

At stage s+1s+1, then isi_{s} is the least ii so that ii is active. Also, by induction, njsn^{s}_{j} is defined for any j<isj<i_{s}.

Case(1). There is a number i<isi'<i_s so that αs+1\alpha_{s}+1 does not match {nj}ji\{n_j\}_{j\leq i'}. Let is+1i_{s+1} be the least such ii'. Let αs+1=αs+1\alpha_{s+1}=\alpha_s+1 and claim iji_{j} is active and njs+1n_j^{s+1} is undefined for all jis+1j\geq i_{s+1}. Moreover, set njs+1=njsn_j^{s+1}=n_j^s for any j<is+1j<i_{s+1}. Go to next stage. Case(2). Otherwise. Search an ordinal γ>αs\gamma>\alpha_s less than ω1β\omega_1^{\beta} and a corresponded unique natural number n>max{njsj<is}n>\max\{n^s_j\mid j<i_s\} so that γ\gamma matches the finite sequence {njs}j<is{n}\{n^s_j\}_{j\lt i_s}\cup \{n\}. If during the search, we found an ordinal γ\gamma' so that there is a number i<isi'<i_s so that γ\gamma does not match {nj}ji\{n_j\}_{j\leq i'}. Then do the action as in Case(1). In other words, let is+1i_{s+1} be the least such ii'. Let αs+1=γ\alpha_{s+1}=\gamma' and claim jj is active and njs+1n_j^{s+1} is undefined for all jis+1j\geq i_{s+1}. Moreover, set njs+1=njsn_j^{s+1}=n_j^s for any j<is+1j<i_{s+1}. Go to next stage. Otherwise, by the construction of (x,f)(x,f), there must be such γ\gamma and nn. Find the least such γ\gamma and the corresponded nn. Let αs+1=γ\alpha_{s+1}=\gamma and is+1=is+1i_{s+1}=i_s+1. Claim jj is active and njs+1n_j^{s+1} is undefined for all jis+1j\geq i_{s+1}. Moreover, set njs+1=njsn_j^{s+1}=n_j^s for any j<isj<i_{s}, niss+1=nn^{s+1}_{i_{s}}=n and claim that isi_s is inactive. Go to next stage. This finishes the construction at stage s+1s+1. \bigskip Let

θ=sωαs.\theta=\bigcup_{s\in \omega}\alpha_s.

\begin{lemma} For any ii, there is some ss so that for any tst\geq s, nitn^t_i is defined, nit=nisn^t_i=n^s_i and ii is inactive at stage tt for any tst\geq s. \end{lemma} \begin{proof} Suppose not. Let ii be the largest number (ii could be 00) so that there is some ss so that for any tst\geq s, nitn^t_i is defined and nit=nisn^t_i=n^s_i for any tst\geq s. Then there is an increasing sequence {sj}jω\{s_j\}_{j\in \omega} so that isj=i+1i_{s_j}=i+1 and sj>ss_j>s for any jj. Note that, by the construction, at stage sj+1s_j+1, ni+1sjn^{s_j}_{i+1} is defined and in the tree Tαsj+1β[xnisj+1,fnisj+1]T_{\alpha_{s_{j}+1}}^{\beta}[x\uh n^{s_j+1}_i,f\uh n^{s_j+1}_i], (xni+1sj+1,fni+1sj+1)(x\uh n^{s_j+1}_{i+1},f\uh n^{s_j+1}_{i+1}) turns to right at most twice. In other words, there are at most two numbers l0<l1(nisj+1,ni+1sj+1)l_0<l_1\in (n^{s_j+1}_{i}, n^{s_j+1}_{i+1}) so that both (xl0,fl0)(x\uh l_0,f\uh l_0) and (xl1,fl1)(x\uh l_1,f\uh l_1) are splitting nodes in Tαsj+1β[xnisj+1,fnisj+1]T_{\alpha_{s_{j}+1}}^{\beta}[x\uh n^{s_j+1}_i,f\uh n^{s_j+1}_i] such that xxl01x\succ x\uh l_0^{\smallfrown}1 and xxl11x\succ x\uh l_1^{\smallfrown}1. Moreover, l1l_1 is the largest number less than ni+1sj+1n^{s_j+1}_{i+1} so that (xl1,fl1)(x\uh l_1,f\uh l_1) is a splitting node in Tαsj+1β[xnisj,fnisj]T_{\alpha_{s_{j}+1}}^{\beta}[x\uh n^{s_j}_i,f\uh n^{s_j}_i]. Since i+1i+1 is activated at sj+1s_{j+1}, αsj\alpha_{s_j} does not match {nksj+1}ki+1\{n^{s_{j}+1}_k\}_{k\leq i+1}. Then either (xl1,fl1)(x\uh l_1,f\uh l_1) is not a splitting node in Tαsj+1β[xnisj+1,fnisj+1]T_{\alpha_{s_{j+1}}}^{\beta}[x\uh n^{s_j+1}_{i},f\uh n^{s_j+1}_{i}] or there exists some dΦxni+1sj+1d\in \Phi^{x\uh n^{s_j+1}_{i+1}} such that Lω1βvLαsj¬φi(f(d),v,β)L_{\omega_1^{\beta}}\models \forall v\in L_{\alpha_{s_j}}\neg \varphi_{i}(f(d),v,\beta) but Lω1βvLαsj+1φi(f(d),v,β)L_{\omega_1^{\beta}}\models \exists v\in L_{\alpha_{s_j+1}} \varphi_{i}(f(d),v,\beta). In either case, the finite string (xl10,τ)(x\uh l_1^{\smallfrown}0,\tau) will be cut off from Tαsj+1β[xnisj+1,fnisj+1]T_{\alpha_{s_{j+1}}}^{\beta}[x\uh n^{s_j+1}_{i},f\uh n^{s_j+1}_{i}]. But this happens for every jj, so it is clear that (x,f)(x,f) must be the leftmost infinite path in Tθβ[xk,fk]T_{\theta}^{\beta}[x\uh k,f\uh k] for some fixed knisk \geq n^{s }_{i}. Then (x,f)(x,f) is the leftmost infinite path in Tω1ββ[xk,fk]T_{\omega_1^{\beta}}^{\beta}[x\uh k,f\uh k], which contradicts our construction of (x,f)(x,f) (since y(i)=1y(i)=1 for infinitely many ii's). \end{proof}

\begin{lemma} For any ii, there must be some ss and dDom(Φxni+1s)d\in Dom(\Phi^{x\uh n^s_{i+1}}) so that for any tst\geq s, either Lω1βu<βvLαsφi(u,v,β)L_{\omega_1^{\beta}}\models \forall u\lt \beta\exists v\in L_{\alpha_s}\varphi_i(u,v,\beta) or Lω1βvLαt¬φi(f(d),v,β)L_{\omega_1^{\beta}}\models \forall v\in L_{\alpha_t}\neg \varphi_i(f(d),v,\beta) \end{lemma} \begin{proof} By Lemma ?, there is some ss so that for any tst\geq s, nitn^t_i is defined, nit=nisn^t_i=n^s_i and ii is inactive at stage tt for any tst\geq s. Then at stage ss, either Lω1βu<βvLαsφi(u,v,β)L_{\omega_1^{\beta}}\models \forall u\lt \beta\exists v\in L_{\alpha_s}\varphi_i(u,v,\beta) or there is some dDom(Φxni+1s)d\in Dom(\Phi^{x\uh n^s_{i+1}}) such that Lω1βvLαs¬φi(f(d),v,β)L_{\omega_1^{\beta}}\models \forall v\in L_{\alpha_s}\neg \varphi_i(f(d),v,\beta). If the first case happens, then we finishes the proof. Otherwise, since ii is never activated from stage ss and Dom(Φxni+1s)Dom(\Phi^{x\uh n^s_{i+1}}) is finite, there must be some fixed dDom(Φxni+1s)d\in Dom(\Phi^{x\uh n^s_{i+1}}) so that Lω1βvLαt¬φi(f(d),v,β)L_{\omega_1^{\beta}}\models \forall v\in L_{\alpha_t}\neg \varphi_i(f(d),v,\beta). \end{proof}

So by Lemma ?, θω1β\theta\geq \omega_1^{\beta} and so θ=ω1β\theta= \omega_1^{\beta}.

This completes the proof of Theorem ?.

Remark: This argument can pushed up to prove Friedman's conjecture for Δ31\Delta^1_3-sets and answer several questions in 26 for level 3. Then by recent work of Yizheng Zhu, we believe those questions can be answered fully.

\part{Model theory and definability}


21. Descriptions in second order logic

The following is a result of Hyttinen, Kangas and V\"a\"an\"anen \cite[Thm. 3.3]{Hyttinen.etal:13}. It shows that under the right hypothesis on a cardinal κ\kappa, the models of a countable complete theory that have size κ\kappa can be described in second order logic iff the theory is easy in the sense of Shelah's main gap. \begin{thm}[24] Let TT be a countable complete theory. For every infinite cardinal κ\kappa with κ=α\kappa = \aleph_\alpha, where (α+ω1)<κ\beth(|\alpha| +\omega_1) \lt \kappa and 2λ<2κ\tp \lambda \lt \tp \kappa for each λ<κ\lambda \lt \kappa, the following are equivalent:

\bi \item[(i)] Every model of TT of size κ\kappa has a description in Lκ,ω2(T)L^2_{\kappa, \omega}(T). \item[(ii)] TT is superstable, shallow, fails the dimensional order property DOP and fails the omitting types order property OTOP. \ei \end{thm}

Explanations: Lκ,ω2(T)L^2_{\kappa, \omega}(T) is the second-order language over the symbol set of TT with disjunctions of size <κ\lt \kappa and finite strings of quantifiers.

Superstability of TT is stronger than stability: no infinite linear order can be defined in a model of TT using a formula in Lω1,ωL_{\omega_1, \omega} with parameters. Shelah proved that a model of a theory TT without DOP can be thought of as built from a tree of small models. Shallowness of TT means that for each model of TT, this tree has no infinite path.


22. Kolezhitskiy: Robinson's theorem that $\ZZ$ is definable in $\QQ$

Yan Kolezhitskiy and Andr\'e Nies discussed a celebrated result of Julia Robinson as part of a semester reading project. The result was originally obtained as part of her 1948 PhD thesis under the supervision of Alfred Tarski. It then appeared in the 1949 J.Symb.\ Logic~39. Much simpler formulas for defining Z\ZZ in Q\QQ have been obtained in subsequent work: a Π2\Pi_2 by Poonen, and recently a Π1\Pi_1 by Jochen Koenigsmann. If Z\ZZ was also Σ1\Sigma_1 definable in Q\QQ then the existential theory of Q\QQ would be undecidable, which is an open problem at present.

\begin{theorem}[39] The set of integers is definable without parameters in the field of rationals (Q,+,×,0,1)(\QQ, + , \times, 0,1). \end{theorem}

Idea and structure of the proof

A subset SS of Q\QQ is called inductive if 0S0 \in S and ySy+1Sy \in S \to y+1 \in S for each yy. The following is a monadic second-order definition of N\NN in Q\QQ:
kNS[S is inductive kS]. k \in \NN \LR \forall S [ \, S \text{ is inductive } \to \, k \in S ].

Julia's idea was that it suffices to quantify over a small collection of sets SS, which is uniformly parameterised by pairs of rationals a,ba,b. Let

ϕ(a,b,k)xyz(2+abk2+bz2=x2+ay2) \phi (a,b,k) \equiv \exists x \exists y \exists z ( 2+abk^2+bz^2 = x^2 +ay^2 )

She used some number theory to show that the sets Sa,bS_{a,b} of the form {k ⁣:Qϕ(a,b,k)}\{k \colon \, \QQ \models \phi(a,b,k)\} suffice.

We can now turn the universal second-order quantification over SS into a universal quantification over rationals a,ba,b in order to obtain a first-order definition replacing (Eq. 3):

kNab[Sa,b is inductive kSa,b]. k \in \NN \LR \forall a \forall b [ \, S_{a,b} \text{ is inductive } \to \, k \in S_{a,b} ].

Clearly, with a smaller collection of sets SS the implication from left to right in (Eq. 5) still holds. The worry is that we don't have enough sets any longer to separate a rational not in N\NN from N\NN. (We note that Julia actually only manages to separate non-integer rationals from N\NN; a small complication of to the idea outlined above will be needed for that. She in effect first defines a set VV in between N\NN and Z\ZZ, then notes that Z=VV\ZZ = V \cup -V. ) We have to pick the condition ϕ(a,b,k)\phi(a,b,k) wisely, ensuring that the relevant sets Sa,bS_{a,b} are inductive. This is done via the following fact. We say that k=n/dk = n/d in its lowest terms, if nZn \in \ZZ, dN{0}d \in \NN -\{0\} and (n,d)=1(n,d)=1. We also say that dd is the denominator of kk in its lowest terms. \begin{fact} Let SS be a set of rationals given by a condition that holds for 00 and only depends on the denominator of the rational in lowest terms. Then SS is inductive. \end{fact} The fact is evident because a rational qq has the same denominator in lowest terms as q+1q+1.

Next she shows that for two particular kinds of choices for a,ba,b, the condition ϕ(a,b,k)\phi (a,b,k) in (Eq. 4) only depends on the denominator of kk in its lowest terms. Firstly, bb is a prime pp such that p3mod4p \equiv 3 \mod 4, and a=1a=1. \begin{lemma} Suppose that pp is a prime such that p3mod4p \equiv 3 \mod 4. The equation 2+pk2+pz2=x2+y22+ pk^2 + pz^2 = x^2+y^2 has a solution for x,x, yy, and zz iff the denominator of kk in its lowest terms is odd, and is co-prime to pp. \end{lemma} Secondly, aa is a prime qq and bb is a prime pp, with some additional restrictions. Recall that the Legendre ``symbol'' (k/p)(k/p) is a binary function that returns 11 if kk is a quadratic residue modpmod p, 00 if k=0k=0, and 1-1 otherwise. \begin{lemma} Suppose that pp and qq are odd primes such that p1mod4p \equiv 1 \mod 4 and (q/p)=1(q/p) = -1. The equation 2+pqk2+pz2=x2+qy22+ pqk^2 + pz^2 = x^2+ qy^2 has a solution for xx, yy, and zz iff the denominator of kk in its lowest terms is co-prime to both qq and pp. \end{lemma} Given these two lemmas, the proof concludes as follows. First one needs a number theoretic claim which provides the qq we need in Lemma~ ?. \begin{claim} Suppose pp is a prime such that p1mod4p \equiv 1 \mod 4. There exists an odd prime qq such that (q/p)=1(q/p)=-1. \end{claim} \begin{proof} Let ss be any (quadratic) non-residue mod pp. Then s+ps+p is also a non-residue. One of ss, s+ps+p is odd, say the former. There is an (odd) prime factor of ss which is also a non-residue, because the Legendre symbol is multiplicative. Let this prime factor be qq. \end{proof} Let ψ(k)\psi(k) be a first-order formula expressing the right hand side of (Eq. 5). Clearly kNψ(k)k \in \NN \RA \psi(k). We verify that ψ(k)kZ\psi(k) \RA k \in \ZZ. Suppose that kQk \in \QQ and ψ(k)\psi(k) holds. Write k=n/dk= n/d in lowest terms. By Lemma~ ?, dd is odd and not divisible by any prime pp such that p3mod4p \equiv 3 \mod 4. By Lemma~ ? using Claim~ ?, dd not divisible by any prime pp such that p1mod4p \equiv 1 \mod 4. Therefore d=1d=1. Thus, kNψ(k)kZk \in \NN \RA \psi(k) \RA k \in \ZZ, so the formula ψ(k)ψ(k)\psi (k) \vee \psi(-k) provides a first-order definition of Z\ZZ in Q\QQ.

Proofs of Lemmas~?} Julia relies on two claims that follow from the Hasse-Minkowski theorem.

\begin{claim} Suppose pp is a prime such that p3mod4p \equiv 3 \mod 4. We have x2+y2pz2=mx^2 + y^2 - pz^2=m for some mQ,m \in \mathbb{Q}, m0m\neq0, iff it is not the case that \indent\indent a) m=pks2m = pks^2, where (k/p)=1(k/p) = 1, or \\ \indent\indent b) m=ks2m = ks^2 with kpk \equiv p (mod(mod 8)8)\\\\ \end{claim} \begin{claim} Suppose pp and qq are odd primes such that p1mod4p \equiv 1 \mod 4 and (q/p)=1(q/p) = -1. There is some non-zero mQm\in \QQ such that x2+qy2pz2=mx^2 + qy^2 - pz^2=m, iff it is not the case that:\\ \indent\indent a) m=pks2m = pks^2 and (k/p)=1(k/p) = -1\\ \indent\indent b) m=qks2m = qks^2 and (k/q)=1(k/q) = -1\\\\ \end{claim}

\iffalse \begin{proof}[Proof of {Lemma ?}] We note that this lemma is equivalent to the following statement: Given a prime pp, p3p \equiv 3 (mod(mod 4)4), for all MQM \in \mathbb{Q} there exist X,X, YY, ZQZ \in \mathbb{Q} such that 2+pM2+pZ2=X2+Y22+ pM^2 + pZ^2= X^2 +Y^2 iff the denominator of MM, dd is such that 2d2 \nmid d and dd is co-prime to pp.\\ To prove this, we take some prime pp that satisfies the antecedent, then we take an arbitrary MM and write it as n/dn/d, where dd is the lowest denominator of MM. We define mm to be 2d2+pn22d^2 +pn^2. Without loss of generality we consider 3 cases.\\\\ \noindent Case 1: 2d2\nmid d and dd is co-prime to pp:\\ \noindent Claim A: mm is co-prime to pp. \noindent We show this by contradiction: suppose there exists some xx, x1x \neq 1 such that xmx \mid m and xpx \mid p. Since pp is a prime, we have it that x=px=p. So p(2d2+pn2)p \mid (2d^2 +pn^2). Thus it must be the case that p2d2p \mid 2d^2. This is only the case if p2p \mid 2 or pdp \mid d. But by previous assumptions both of these are false, ergo we get a contradiction. Thus the claim holds.\\ Thus it is not the case that mm can be represented as pks2pks^2, for any kk and ss.\\\\ \noindent Claim B: m1m \equiv 1 or m2m \equiv 2 (mod(mod 4)4). \noindent Since 4m4 \mid m would imply that 4÷2d24 \div 2d^2 and 4÷pn24 \div pn^2, which would only be true if nn and dd had a common divisor, by our initial assumptions that dd is the lowest denominator ofMM, we conclude that 4m4 \nmid m.\ [PROVE 3m3 \nmid m]\\ \noindent Claim C: mm is not of the form ks2ks^2, where kpk \equiv p (mod(mod 8)8): \noindent [GIVE PROOF in modulo arithmetic] FROM Claim 1, and fact that p3p \equiv 3 (mod(mod 4)4)\\ From claims A and C, by Lemma 0.1, we get it that there exist XX, YY, and ZZ such that m=X2+Y2pZ2m = X^2 + Y^2 - pZ^2. In other words mm can be represented by the given equation.\\\\ \noindent Case 2: pdp \mid d.\\ We write dd as prpr. Then m=pkm = pk, where k=2pr2+n2k = 2pr^2 + n^2. \noindent Claim D: kk and pp are co-prime:\\\\ \noindent Claim E: (k/p)=(n2/p)=1(k/p) = (n^2/p) = 1 \noindent From these, we get that m=pk=pk12=pkS2m = pk = pk1^2 = pkS^2, where (k/p)=1(k/p) = 1, and thus by Lemma 0.1, we get it that mm cannot be represented by the given quadratic form.\\\\\\ \noindent Case 3: 2d2 \mid d \noindent We write d=2sd = 2s, then m=8s2+pn2m = 8s^2 +pn^2. \noindent Claim F: mmodpm \mod p (mod(mod 8)8) \noindent Since nn is odd...\\\\ Thus, by claim F and ?, we have it that mm is not represented by the said equation.\\ So from cases 1, 2, and 3, we draw the conclusion that mm is represented by X2+Y2pZ2X^2 + Y^2 -pZ^2 if 2d2\nmid d and dd is co-prime to pp.\\ We then note that by basic algebraic rearrangements, from this, we get:\\ 2+pM2+p(Zd)2=(Xd)2+(Yd)22+pM^2 + p(\frac{Z}{d})^2 = (\frac{X}{d})^2 +(\frac{Y}{d})^2\\ \end{proof}

\fi

\def\cprime{'} \def\cprime{'}


References

  1. Uri Andrews, Mingzhong Cai, David Diamondstone, Carl Jockusch, and Steffen Lempp.. Asymptotic density, computable traceability, and 1-randomness. Preprint, 2013.
  2. L. Bienvenu, P. G\'acs, M. Hoyrup, C. Rojas, and A. Shen. Algorithmic tests and randomness with respect to a class of measures.. Proceedings of the Steklov Institute of Mathematics, 274(1):34--89, 2011. Published in Russian in \it Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2011, Vol. 274, pp. 41--102.
  3. L. Bienvenu, N. Greenberg, A. Ku\vcera, A. Nies, and D. Turetsky. Coherent randomness tests and computing the K-trivial sets.. To appear in J. European Math. Society, 2016.
  4. Andreas Blass. Some questions arising from hindman's theorem.. Scientiae Mathematicae Japonicae, (62):331--334, 2005.
  5. J. Brendle, A. Brooke-Taylor, Keng Meng Ng, and A. Nies. An analogy between cardinal characteristics and highness properties. of oracles. In Proceedings of the 13th Asian Logic Conference: Guangzhou, China, pages 1--28. World Scientific, 2013. http://arxiv.org/abs/1404.2839.
  6. Yue Yang Chi Tat Chong, Steffen Lempp. On the role of the collection principle for $\sigma^0_2$ formulas in. second-order reverse mathematics. Proceedings of the American Mathematical Society, 138:1093--1100, 2010.
  7. Yue Yang Chi Tat Chong, Theodore Slaman. The metamathematics of the stable ramsey's theorem for pairs.. Journal of the American Mathematical Society, 27:863--892, 2014.
  8. Barbara F Csima and Joseph R Mileti. The strength of the rainbow Ramsey theorem.. The Journal of Symbolic Logic, 74(04):1310--1324, 2009.
  9. Jeff Hirst Damir Dzhafarov. The polarized ramsey's theorem.. Archive for Mathematical Logic, 48(2):141--157, 2009.
  10. Reed Solomon Linda B. Westrick Damir Dzhafarov, Carl G. Jockusch. Effectiveness of hindman's theorem for bounded sums.. In N. Greenberg B. Khoussainov A. Melnikov A. Day, M. Fellows, editor, Proceedings of the International Symposium on Computability and Complexity (in honour of Rod Downey's 60th birthday), Lecture Notes in Computer Science. Springer, To appear.
  11. A. Nies (editor). Logic Blog 2013.. Available at http://arxiv.org/abs/1403.5719, 2013.
  12. A. Nies (editor). Logic Blog 2015.. Available at http://arxiv.org/abs/1602.04432, 2015.
  13. S. Figueira, D. Hirschfeldt, J. Miller, Selwyn Ng, and A Nies. Counting the changes of random $\Delta^0_2$ sets.. J. Logic Computation, 25:1073--1089, 2015. Journal version of conference paper at CiE 2010.
  14. Santiago Figueira, Joseph S. Miller, and Andr\'e Nies. Indifferent sets.. J. Logic Comput., 19(2):425--443, 2009.
  15. M. Fried and M. Jarden. Field arithmetic, volume 11.. Springer Science \& Business Media, 2006.
  16. Su Gao. Invariant descriptive set theory, volume 293 of Pure and. Applied Mathematics (Boca Raton). CRC Press, Boca Raton, FL, 2009.
  17. Su Gao, S. Jackson, and B. Seward. Group colorings and Bernoulli subflows, volume 241.. American Mathematical Society, 2016.
  18. D. Gorenstein, R. Lyons, and R. Solomon. The classification of the finite simple groups 3, volume 40.. American Mathematical Soc., 1998.
  19. Alexandre Grothendieck. R\'esum\'e de la th\'eorie m\'etrique des produits tensoriels. topologiques. Resenhas do Instituto de Matem\'atica e Estat\'\istica da Universidade de S\ ao Paulo, 2(4):401--481, 1996. This is a reprint of a 1953 paper.
  20. R. M. Guralnick, W. M. Kantor, M. Kassabov, and A. Lubotzky. Presentations of finite simple groups: a quantitative approach.. J. Amer. Math. Soc., 34:711--774, 2008.
  21. Leo A. Harrington. Analytic determinacy and $0^\#$.. J. Symbolic Logic, 20:685--693, 1978.
  22. M. Hoyrup and C. Rojas. Computability of probability measures and Martin-L\"of randomness. over metric spaces. Inform. and Comput., 207(7):830--847, 2009.
  23. Mathieu Hoyrup and Cristobal Rojas. An Application of Martin-L\"of Randomness to Effective Probability. Theory. In Klaus Ambos-Spies, Benedikt L\"owe, and Wolfgang Merkle, editors, CiE, pages 260--269. Springer, 2009.
  24. T. Hyttinen, K. Kangas, and J. V\"a\"an\"anen. On second-order characterizability.. Logic Journal of IGPL, 21(5):767--787, 2013.
  25. M. Jarden and A. Lubotzky. Random normal subgroups of free profinite groups.. Journal of Group Theory, 2:213--224, 1999.
  26. Alexander S. Kechris, Donald A. Martin, and Robert M. Solovay. Introduction to $Q$-theory.. In Ordinal Definability and Recursion Theory. The Cabal Seminar. Volume III, volume 43 of Lect. Notes Log., pages 126--199. Cambridge University Press, Cambridge, 2016.
  27. Wolfgang Kimmerle, Richard Lyons, Robert Sandling, and David N Teague. Composition factors from the group ring and artin's theorem on orders. of simple groups. Proceedings of the London Mathematical Society, 3(1):89--122, 1990.
  28. Donald A. Martin. Proof of a conjecture of Friedman.. Proc. Amer. Math. Soc., 55(1):129, 1976.
  29. B. Monin and A. Nies. A unifying approach to the Gamma question.. In Proceedings of Logic in Computer Science (LICS). IEEE press, 2015.
  30. A. Nies. Calculus of cost functions.. To appear in Barry Cooper and Mariya Soskova (eds.), The Incomputable: Journeys beyond the Turing barrier, Springer-Verlag.
  31. A. Nies. Computability and randomness, volume 51 of Oxford Logic. Guides. Oxford University Press, Oxford, 2009. 444 pages. Paperback version 2011.
  32. A. Nies and K. Tent. Describing finite groups by short first-order sentences.. Israel J. of Mathematics, to appear, 2014, updated 2015. available at arXiv:1409.8390.
  33. Theodore A. Slaman Peter A. Cholak, Carl G. Jockusch. On the strength of ramsey's theorem for pairs.. Journal of Symbolic Logic, 66(1):1--55, 2001.
  34. G. Pisier. Grothendieck’s theorem, past and present.. Bulletin of the American Mathematical Society, 49(2):237--323, 2012.
  35. Michael O. Rabin. Computable algebra, general theory and theory of computable fields.. Trans. Amer. Math. Soc., 95:341--360, 1960.
  36. P. Raghavendra and D. Steurer. Towards computing the grothendieck constant.. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 525--534. Society for Industrial and Applied Mathematics, 2009.
  37. L. Ribes and P. Zalesskii. Profinite groups.. Springer, 2000.
  38. D. Robinson. A course in the theory of groups.. Springer--Verlag, 1988.
  39. J. Robinson. Definability and decision problems in arithmetic.. J. Symbolic Logic, 14(2):98--114, 1949.
  40. S. G. Simpson. Subsystems of second order arithmetic.. Perspectives in Logic. Cambridge University Press, Cambridge, second edition, 2009.
  41. R. Smith. Effective aspects of profinite groups.. The Journal of Symbolic Logic, 46(04):851--863, 1981.
  42. S. Thomas. Topological full groups of minimal subshifts and just-infinite. groups. In Proceedings of the 12th Asian Logic Conference, pages 298--313. World Scientific, 2013.
  43. Ingo Wegener et al. The complexity of Boolean functions, volume 1.. BG Teubner Stuttgart, 1987.
  44. Liang Yu. A new proof of Friedman's conjecture.. Bull. Symbolic Logic, 17(3):455--461, 2011. \endthebibliography